Re: 657 - The die is cast
Posted: Tue Apr 28, 2009 10:51 am
The quoted part of your post is pretty obvious! Which part are you having trouble with?
thnx. reading ur post i thought if its ovious why cant i understand..The quoted part of your post is pretty obvious! Which part are you having trouble with?
does that mean if input is a 5X5 grid, then pixel (1,1) and pixel (1,5) are connected?? im confused with the statement a=a1 and b=ak. sorry for the trouble.A set S of pixels is connected if for every pair (a,b) of pixels in S, there is a sequence a1, a2, ...., ak in S such that a = a1 and b = ak
Code: Select all
*.***
***..
.....
.....
.....
Code: Select all
*.***
.....
.....
.....
.....
anyone can understand frm this line which pixels r connected.. We consider two pixels connected if they share an edge - meeting at a corner is not enough
Actually, no. They are not connected, but instead they are part of a same connected set of pixels (i.e. indirectly connected)sohel wrote:For the first case, (1,1) is connected to (1,5)
I don't see any problems with the problem statement at all, it's pretty clear.calicratis19 wrote:i got it thnxs![]()
. but i think in the problem statement it is unnecessary to give that line.making the statement confusing. because before it was written that
. We consider two pixels connected if they share an edge - meeting at a corner is not enough
There's another way to define connected components - via equivalence relations - but it's even more verbose.A set $S$ of pixels is connected if for every pair $(a,b)$ of pixels in $S$, there is a sequence $a_1, a_2, \dots, a_k$ in $S$ such that $a = a_1$ and $b = a_k$, and $a_i$ and $a_{i+1}$ are connected for $1 \le i < k$.
i understood this line pretty well. but i couldnt understood the lineWe consider two pixels connected if they share an edge - meeting at a corner is not enough.
and i think this line is unncessary because the first line says it all.A set S of pixels is connected if for every pair (a,b) of pixels in S, there is a sequence a1, a2, ...., ak in S such that a = a1 and b = ak ,
Read more math books, and you'd get used to a language like that :)calicratis19 wrote:i understood this line pretty well. but i couldnt understood the lineA set S of pixels is connected if for every pair (a,b) of pixels in S, there is a sequence a1, a2, ...., ak in S such that a = a1 and b = ak ,
Code: Select all
#include<stdio.h>
#include<queue>
#include<algorithm>
#define MAX 60
using namespace std;
queue<int>row;
queue<int>column;
queue<int>r;
queue<int>c;
char path[MAX][MAX];
int fg[MAX][MAX];
int n,m;
int rw[5]={0,-1,1,0,0};
int col[5]={0,0,0,-1,1};
int ans[MAX];
void play(int u,int v){
int nr,nc,ro,co;
row.push(u);
column.push(v);
fg[u][v]=1;
while(!row.empty()){
ro=row.front();
co=column.front();
row.pop();
column.pop();
for(int i=0;i<5;i++){
nr=ro+rw[i];
nc=co+col[i];
if(path[nr][nc]=='X' && fg[nr][nc]==0 && nr<m && nc>=0 && nc<n){
row.push(nr);
column.push(nc);
fg[nr][nc]=1;
}
else if(path[nr][nc]=='*' && fg[nr][nc]==0 && nr<m && nc>=0 && nc<n){
r.push(nr);
c.push(nc);
fg[nr][nc]=1;
}
}
}
}
int ffill(int u,int v){
int nr,nc,ro,co,count;
r.push(u);
c.push(v);
count=0;
while(!r.empty()){
ro=r.front();
co=c.front();
r.pop();
c.pop();
for(int i=0;i<5;i++){
nr=ro+rw[i];
nc=co+col[i];
if(path[nr][nc]=='X' && fg[nr][nc]==0){
// printf("%d %d\n",nr,nc);
play(nr,nc);
count++;
r.push(nr);
c.push(nc);
}
else if(path[nr][nc]=='*' && fg[nr][nc]==0 && nr<m && nc>=0 && nc<n){
r.push(nr);
c.push(nc);
fg[nr][nc]=1;
}
}
}
return count;
}
void unvisit(){
for(int i=0;i<MAX;i++){
for(int j=0;j<MAX;j++){
path[i][j]='$';
fg[i][j]=0;
}
}
}
int main(){
// freopen("a.txt","r",stdin);
int ns,x=1,gap;
while(scanf("%d %d\n",&n,&m)==2){
if(n==0 && m==0)
break;
unvisit();
for(int i=0;i<m;i++){
for(int j=0;j<n;j++)
scanf("%c",&path[i][j]);
scanf("%*c");
}
ns=0;
for(int k=0;k<m;k++){
for(int z=0;z<n;z++)
if((path[k][z]=='*' || path[k][z]=='X') && fg[k][z]==0 && k>=0 && k<m && z>=0 && z<n){
// printf("%d %d\n",k,z);
ans[ns++]=ffill(k,z);
}
}
sort(ans,ans+ns);
gap=0;
printf("Throw %d:\n",x++);
for(int l=0;l<ns;l++){
if(ans[l]==0)
continue;
if(gap++)
printf(" ");
printf("%d",ans[l]);
}
printf("\n\n");
}
return 0;
}
Code: Select all
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector <string> inp;
vector <int> res;
int cnt;
int n , m;
bool mark[60][60];
void dfsx(int r , int c);
void dfs(int r , int c)
{
if(inp[r][c] == '*')
mark[r][c] = true;
for(int i = r-1 ; i <= r+1 ; i++)
for(int j = c-1 ; j <= c+1 ; j++)
if(i >= 0 && j >= 0 && i < m && j < n )
{
if(inp[i][j] == '*' && mark[i][j] == false)
dfs(i , j);
else if(inp[i][j] == 'X' && mark[i][j] == false)
{
//cout << "x = " << i << " " << j << endl;
cnt++;
dfsx(i , j);
}
}
}
void dfsx(int r , int c)
{
vector <pair <int , int> > d;
pair <int , int> tmp;
//cout << "x = " << r << " " << c << endl;
mark[r][c] = true;
bool xx = false;
for(int i = r-1 ; i <= r+1 ; i++)
for(int j = c-1 ; j <= c+1 ; j++)
//for(int j = c-1 ; j <= c+1 ; j++)
// for(int i = r-1 ; i <= r+1 ; i++)
if(i >= 0 && j >= 0 && i < m && j < n )
if(i == r || j == c)
{
if(inp[i][j] == 'X' && mark[i][j] == false)
{
xx = true;
//cnt--;
dfsx(i , j);
}
if(inp[i][j] == '*' && mark[i][j] == false)
{
tmp.first = i;
tmp.second = j;
d.push_back(tmp);
}
}
//if(!xx)
//{
for(int i = 0 ; i < d.size() ; i++)
if(mark[d[i].first][d[i].second] == false)
{
dfs(d[i].first , d[i].second);
}
//}
}
int main()
{
//freopen("data.in" , "r" , stdin);
string line;
int cn = 1;
while(cin >> n >> m && n || m)
{
getline(cin , line);
memset(mark , false , sizeof mark);
inp.clear();
res.clear();
for(int i = 0 ; i < m ; i++)
{
getline(cin , line);
inp.push_back(line);
}
for(int i = 0 ; i < inp.size() ;i++)
for(int j = 0 ; j < inp[i].size() ; j++)
{
if((inp[i][j] == '*' || inp[i][j] == 'X') && mark[i][j] == false)
{
//cout << "start = " << i << " " << j << endl;
dfs(i , j);
res.push_back(cnt);
cnt = 0;
}
}
sort(res.begin() , res.end());
cout << "Throw " << cn++ << endl;
for(int i = 0 ; i < res.size() ; i++)
{
if(i > 0)
cout << " ";
cout << res[i];
}
cout << endl << endl;
}
return 0;
}
I fix that problem dude...prasanjit barua wrote:Though the description says "The picture will contain at least one die, and the numbers of dots per die is between 1 and 6, inclusive. ",bt thre is a case like this:
4 4
****
****
****
****
fr which ur code says
throw#
0
bt ans will be
throw#
just a blank line .try this..
Code: Select all
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector <string> inp;
vector <int> res;
int cnt;
int n , m;
bool mark[60][60];
void dfsx(int r , int c);
void dfs(int r , int c)
{
if(inp[r][c] == '*')
mark[r][c] = true;
for(int i = r-1 ; i <= r+1 ; i++)
for(int j = c-1 ; j <= c+1 ; j++)
if(i >= 0 && j >= 0 && i < m && j < n )
{
if(inp[i][j] == '*' && mark[i][j] == false)
dfs(i , j);
else if(inp[i][j] == 'X' && mark[i][j] == false)
{
//cout << "x = " << i << " " << j << endl;
cnt++;
dfsx(i , j);
}
}
}
void dfsx(int r , int c)
{
vector <pair <int , int> > d;
pair <int , int> tmp;
//cout << "x = " << r << " " << c << endl;
mark[r][c] = true;
bool xx = false;
for(int i = r-1 ; i <= r+1 ; i++)
for(int j = c-1 ; j <= c+1 ; j++)
//for(int j = c-1 ; j <= c+1 ; j++)
// for(int i = r-1 ; i <= r+1 ; i++)
if(i >= 0 && j >= 0 && i < m && j < n )
if(i == r || j == c)
{
if(inp[i][j] == 'X' && mark[i][j] == false)
{
xx = true;
//cnt--;
dfsx(i , j);
}
if(inp[i][j] == '*' && mark[i][j] == false)
{
tmp.first = i;
tmp.second = j;
d.push_back(tmp);
}
}
//if(!xx)
//{
for(int i = 0 ; i < d.size() ; i++)
if(mark[d[i].first][d[i].second] == false)
{
dfs(d[i].first , d[i].second);
}
//}
}
int main()
{
//freopen("data.in" , "r" , stdin);
string line;
int cn = 1;
while(cin >> n >> m && n || m)
{
getline(cin , line);
memset(mark , false , sizeof mark);
inp.clear();
res.clear();
for(int i = 0 ; i < m ; i++)
{
getline(cin , line);
inp.push_back(line);
}
for(int i = 0 ; i < inp.size() ;i++)
for(int j = 0 ; j < inp[i].size() ; j++)
{
if((inp[i][j] == '*' || inp[i][j] == 'X') && mark[i][j] == false)
{
//cout << "start = " << i << " " << j << endl;
dfs(i , j);
if(cnt > 0)
{
res.push_back(cnt);
cnt = 0;
}
}
}
sort(res.begin() , res.end());
cout << "Throw " << cn++ << endl;
for(int i = 0 ; i < res.size() ; i++)
{
if(i > 0)
cout << " ";
cout << res[i];
}
cout << endl << endl;
}
return 0;
}
Actually you are wrong, there is no such cases.prasanjit barua wrote:Though the description says "The picture will contain at least one die, and the numbers of dots per die is between 1 and 6, inclusive. ",bt thre is a case like this:
4 4
****
****
****
****
fr which ur code says
throw#
0
bt ans will be
throw#
just a blank line .try this..
Try these cases:mostafa_angel wrote:I fix that problem dude...prasanjit barua wrote:Though the description says "The picture will contain at least one die, and the numbers of dots per die is between 1 and 6, inclusive. ",bt thre is a case like this:
4 4
****
****
****
****
fr which ur code says
throw#
0
bt ans will be
throw#
just a blank line .try this..
but again I got WA...![]()
Code: Select all
Code: Select all
5 5
*.***
***..
.....
.....
.....
5 5
XXX*X
XXX*X
.....
X***X
XX***
10 5
..........
..X**.*X..
..........
...*X*X...
..........
10 5
..........
..X....X..
..........
...*X*X...
..........
10 5
..........
..X....X..
..X....X..
..XXXXXX..
..........
10 5
..........
..X*X.....
..*X*.....
..X*X.....
..........
10 5
..........
..X*X.....
..*X**....
..X*X*....
..........
5 5
XXXXX
XXXXX
XXXXX
XXXXX
XXXXX
30 15
..............................
..............................
...............*..............
...*****......****............
...*X***.....**X***...........
...*****....***X**............
...***X*.....****.............
...*****.......*..............
..............................
........***........******.....
.......**X****.....*X**X*.....
......*******......******.....
.....****X**.......*X**X*.....
........***........******.....
..............................
10 6
..........
.XXX......
....XXX...
.......XXX
....XXX...
*X*X......
6 6
XXXXX*
.....X
.....X
.....X
.....X
.....X
6 6
XXXXX.
.....X
.....X
.....X
.....X
.....X
6 6
XXXXX.
....*X
.....X
.....X
.....X
.....X
30 15
.....X*X*X*X*X*X***...........
.X......................X.....
...............*.........X....
...X****......****........X...
...*X*.*.....**X***X..........
...*.X......***X**.....XXX....
...*.*X*.....****........X....
...***.X.......*.........X....
..............................
.......X***.............*..***
......******X****.....*X**X*..
..***********......**.*.*.....
.....****X**.......*X**X*.....
........***........*....*.....
........***.********..........
0 0
Code: Select all
Throw 1
0
Throw 2
2 2
Throw 3
1 1 2
Throw 4
1 1 2
Throw 5
1
Throw 6
5
Throw 7
5
Throw 8
1
Throw 9
1 2 2 4
Throw 10
1 1 1 1 2
Throw 11
2
Throw 12
1 1
Throw 13
2
Throw 14
1 1 1 1 1 2 3 4 5 6
Code: Select all
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX 60
char a[MAX][MAX];
bool print(long M,long N)
{long I,J;
for(I=0;I<=M+1;I++)
{
for(J=0;J<=N+1;J++)
printf("%c",a[I][J]);
printf("\n");
}
printf("\n");
return 1;
}
class DFS
{
long count;
public:
vector<long> V;
bool DFS_cross(long I,long J)
{
a[I][J]='.';
//UP
if( a[I-1][J]=='X' )
{
DFS_cross(I-1,J);
//count++;
}
else if( a[I-1][J]=='*' )
{
DFS_star(I-1,J);
}
//DOWN
if( a[I+1][J]=='X' )
{
DFS_cross(I+1,J);
//count++;
}
else if( a[I+1][J]=='*' )
{
DFS_star(I+1,J);
}
//LEFT
if( a[I][J-1]=='X' )
{
DFS_cross(I,J-1);
//count++;
}
else if( a[I][J-1]=='*' )
{
DFS_star(I,J-1);
}
//RIGHT
if( a[I][J+1]=='X' )
{
DFS_cross(I,J+1);
//count++;
}
else if( a[I][J+1]=='*' )
{
DFS_star(I,J+1);
}
return 1;
}
bool DFS_star(long I,long J)
{
a[I][J]='.';
//UP
if( a[I-1][J]=='X' )
{
DFS_cross(I-1,J);
count++;
}
else if( a[I-1][J]=='*' )
{
DFS_star(I-1,J);
}
//DOWN
if( a[I+1][J]=='X' )
{
DFS_cross(I+1,J);
count++;
}
else if( a[I+1][J]=='*' )
{
DFS_star(I+1,J);
}
//LEFT
if( a[I][J-1]=='X' )
{
DFS_cross(I,J-1);
count++;
}
else if( a[I][J-1]=='*' )
{
DFS_star(I,J-1);
}
//RIGHT
if( a[I][J+1]=='X' )
{
DFS_cross(I,J+1);
count++;
}
else if( a[I][J+1]=='*' )
{
DFS_star(I,J+1);
}
return 1;
}
DFS(long M,long N)
{
long I,J;
for(I=1;I<=M;I++)
{
for(J=1;J<=N;J++)
{
if( a[I][J]=='*' )
{
count=0;
DFS_star(I,J);
V.push_back(count);
//print(M,N);
//printf("%ld *> %ld\n",V.size(),count);
}
else if( a[I][J]=='X' )
{
count=1;
DFS_cross(I,J);
V.push_back(count);
//print(M,N);
//printf("%ld X> %ld\n",V.size(),count);
}
}
}
}
};
class INPUT
{
long I,J;
public:
INPUT(long M,long N)
{
for(I=1;I<=M;I++)
{
J=1;
while( (a[I][J]=getchar())!='\n' )
{
J++;
}
a[I][J]='.';
//printf("%ld_%ld\n",I,J);
}
for(J=0;J<=N+1;J++)
a[I][J]='.';
//print(M,N);
}
};
class TEST
{
long I,row,col,T,size;
public:
TEST()
{
for(I=0;I<MAX;I++)
{
a[I][0]='.';
a[0][I]='.';
}
T=0;
while( scanf("%ld %ld",&col,&row)==2 && row && col )
{
getchar();
//printf("%ld_%ld\n",M,N);
INPUT B(row,col);
DFS C(row,col);
T++;
size=C.V.size();
sort(C.V.begin(), C.V.end());
printf("Throw %ld\n",T);
for(I=0; I<size-1 ;I++)
{
//printf("->%ld %ld ",I,C.V.size()-1);
if( C.V[I] )
printf("%ld ",C.V[I]);
}
if( size )
{
if( C.V[I] )
printf("%ld\n\n",C.V[I]);
else
printf("\n\n");
}
else
{
printf("\n\n");
}
}
}
};
int main()
{
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
*/
TEST A;
return 0;
}