Page 2 of 3
Posted: Sun Nov 13, 2005 2:30 am
Or by using an explicit stack..

I solved this problem using DFS though, so it should be okay..

Posted: Mon Nov 14, 2005 6:36 am
I'll try again in this problem after I've finished my mid semester exam...

Posted: Wed Nov 16, 2005 3:58 pm
can't find out why i get WA... can someone help ?

Code: Select all

``````#include <stdio.h>
#define isL(x) ((x) >= 'A' && (x) <= 'Z')
#define isBetter(p1,p2) (sol1[p1] > sol1[p2] || (sol1[p1] == sol1[p2] && sol2[p1] < sol2[p2]))
#define NMAX 55

int n, m;
char map[NMAX][NMAX];
char u[NMAX][NMAX];

int soln;
int sol1[NMAX*NMAX];
char sol2[NMAX*NMAX];

void swapp(int i, int j)
{
int aux;
aux = sol1[i]; sol1[i] = sol1[j]; sol1[j] = aux;
aux = sol2[i]; sol2[i] = sol2[j]; sol2[j] = aux;
}

void hup(int pos)
{
int p = pos/2;
if(!p)
return;
if(isBetter(p, pos))
{
swapp(p, pos);
hup(p);
}
}

void hdown(int pos)
{
int max = pos;
do
{
pos = max;
if(2*pos <= soln)
if(isBetter(pos, 2*pos))
max = 2*pos;
if(2*pos < soln)
if(isBetter(max, 2*pos+1))
max = 2*pos+1;
if(max == pos)
return;
swapp(pos, max);
} while(1);
}

void hsort()
{
int tmp = soln;
while(soln > 1)
{
swapp(soln, 1);
soln--;
hdown(1);
}
soln = tmp;
}

int fill(int y, int x, char ch)
{
if(map[y][x] != ch || u[y][x])
return 0;
u[y][x] = 1;
return (1 + fill(y-1,x, ch) + fill(y+1,x, ch) + fill(y,x-1, ch) + fill(y,x+1, ch));
}

{
soln++;
sol1[soln] = val;
sol2[soln] = ch;
hup(soln);
}

void solve()
{
int i, j, aux;
memset(u, 0, sizeof(u));
soln = 0;
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
if(!u[i][j] && isL(map[i][j]))
hsort();
}

void show()
{
int i;
for(i = 1; i <= soln; i++)
printf("%c %d\n", sol2[i], sol1[i]);
}

int main()
{
int i, j, k = 0;
scanf("%d %d\n", &n, &m);
while(n || m)
{
printf("Problem %d:\n", ++k);
for(i = 1; i <= n; i++)
{
for(j = 1; j <= m; j++)
scanf("%c", &map[i][j]);
scanf("\n");
}
solve();
show();
scanf("%d %d\n", &n, &m);
}
return 0;
}
``````

Posted: Fri Nov 18, 2005 10:40 am
Fr3eM4n, I've compiled yours with DJGPP compiler but the compiler give me error code which I didn't know (sorry, but I try to understand it). And I've also compile it with Borland C++ 3.1 and I got the same result too.

I try add #include <string.h> to cover the error of memset prototype then I compiled again. The DJGPP gave me error again but Borland C++ 3.1 gave me success.

Then I tested with this following input data:

Code: Select all

``````50 50
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
50 50
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..............AAAAA...............................
..............AAAAA...............................
..............AAAAA...............................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
50 50
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
.............A.A.A.A.A.A.A.A.A.A..................
..............A.A.A.A.A.A.A.A.A...................
...............A.A.A.A.A.A.A.A....................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
50 50
A.................................................
.A................................................
..A...............................................
...A..............................................
....A.............................................
.....A............................................
......A...........................................
.......A..........................................
........A.........................................
.........A........................................
..........A.......................................
...........A......................................
............A.....................................
.............A....................................
..............A...................................
...............A..................................
................A.................................
.................A................................
..................A...............................
...................A..............................
....................A.............................
.....................A............................
......................A...........................
.......................A..........................
........................A.........................
.........................A........................
..........................A.......................
...........................A......................
............................A.....................
.............................A....................
..............................A...................
...............................A..................
................................A.................
.................................A................
..................................A...............
...................................A..............
....................................A.............
.....................................A............
......................................A...........
.......................................A..........
........................................A.........
.........................................A........
..........................................A.......
...........................................A......
............................................A.....
.............................................A....
..............................................A...
...............................................A..
................................................A.
.................................................A
3 50
AAAAAAAABAAAA.....................................
.AAAAAAAABAAAA....................................
..AAAAAAAABAAAA...................................
1 50
ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX
1 26
ABCDEFGHIJKLMNOPQRSTUVWXYZ
0 0``````
[/size]

My AC-ed program ( thanx Angga for your help, it helps me much! ) output these:

Code: Select all

``````Problem 1:
Problem 2:
A 15
Problem 3:
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
Problem 4:
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
Problem 5:
A 24
A 12
B 1
B 1
B 1
Problem 6:
A 1
A 1
B 1
B 1
C 1
C 1
D 1
D 1
E 1
E 1
F 1
F 1
G 1
G 1
H 1
H 1
I 1
I 1
J 1
J 1
K 1
K 1
L 1
L 1
M 1
M 1
N 1
N 1
O 1
O 1
P 1
P 1
Q 1
Q 1
R 1
R 1
S 1
S 1
T 1
T 1
U 1
U 1
V 1
V 1
W 1
W 1
X 1
X 1
Y 1
Z 1
Problem 7:
A 1
B 1
C 1
D 1
E 1
F 1
G 1
H 1
I 1
J 1
K 1
L 1
M 1
N 1
O 1
P 1
Q 1
R 1
S 1
T 1
U 1
V 1
W 1
X 1
Y 1
Z 1
``````
[/size]

Code: Select all

``````Problem 1:
Problem 2:
A 15
Problem 3:
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
Problem 4:
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
Problem 5:
A 25
A 12
B 1
B 1
B 1
Problem 6:
A 1
A 1
B 1
B 1
C 1
C 1
D 1
D 1
E 1
E 1
F 1
F 1
G 1
G 1
H 1
H 1
I 1
I 1
J 1
J 1
K 1
K 1
L 1
L 1
M 1
M 1
N 1
N 1
O 1
O 1
P 1
P 1
Q 1
Q 1
R 1
R 1
S 1
S 1
T 1
T 1
U 1
U 1
V 1
V 1
W 1
W 1
X 1
X 1
Y 1
Z 1
Problem 7:
A 1
B 1
C 1
D 1
E 1
F 1
G 1
H 1
I 1
J 1
K 1
L 1
M 1
N 1
O 1
P 1
Q 1
R 1
S 1
T 1
U 1
V 1
W 1
X 1
Y 1
Z 1
``````
[/size]

The difference is in line 84, just see the two results above. Your code seems break at the 5th test case.
Hope it helps you

Posted: Fri Nov 18, 2005 1:10 pm
yes, helped me a lot. thank you.

the bug was in the fill function.. i didn't checked if (x > m || y > n)
and after several tests, fill() counted some chars outside the map (map was not reinitialized each test case)

### 10946 - You want what filled?

Posted: Fri Feb 10, 2006 6:10 am
i think this problem is very easy.i just use dfs to solve it. but i always got WA. i don't know why. could somebody give me some I/O please or tell me what's wrong with my code . Thank you very much

Code: Select all

``````#include <iostream>
using namespace std;
#include <cstring>

typedef struct
{
char cc;
int num;
}hode;

hode h[251];
char m[51][51];
char flag[51][51];
int count;
int x,y;

void input()
{
int i,j;
for(i=0;i<x;i++)
for(j=0;j<y;j++)
{
cin>>m[i][j];
flag[i][j]=true;
}
count=0;
}

void dfs(int i,int j,char c)
{
if(i-1>=0 && flag[i-1][j] && m[i-1][j]==c)
{
h[count].num++;
flag[i-1][j]=false;
dfs(i-1,j,c);
}

if(j-1>=0 && flag[i][j-1] && m[i][j-1]==c)
{
h[count].num++;
flag[i][j-1]=false;
dfs(i,j-1,c);
}

if(i+1<x && flag[i+1][j] && m[i+1][j]==c)
{
h[count].num++;
flag[i+1][j]=false;
dfs(i+1,j,c);
}

if(j+1<y && flag[i][j+1] && m[i][j+1]==c)
{
h[count].num++;
flag[i][j+1]=false;
dfs(i,j+1,c);
}

return ;

}

int main()
{
int i,j;
int kase;
kase=1;

while(cin>>x>>y && x && y)
{
input();
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
{
if(flag[i][j] && m[i][j]!='.')
{
h[count].cc=m[i][j];
h[count].num=1;
flag[i][j]=false;
dfs(i,j,m[i][j]);
count++;
}
}
}

hode t;
for(i=0;i<count-1;i++)
for(j=0;j<count-i-1;j++)
{
if((h[j].num < h[j+1].num) || (h[j].num == h[j+1].num && h[j].cc > h[j+1].cc))
{
t=h[j];
h[j]=h[j+1];
h[j+1]=t;
}
}
cout<<"Problem "<<kase++<<":"<<endl;
for(i=0;i<count;i++)
{
cout<<h[i].cc<<" "<<h[i].num<<endl;
}
}
return 0;
}
``````

Posted: Fri Feb 10, 2006 4:25 pm
The array of hode h[251] is not big enough;
Change it to h[2500] will get AC though it waste some memory!

Posted: Mon Aug 07, 2006 2:38 pm
frankhuhu wrote:The array of hode h[251] is not big enough;
Change it to h[2500] will get AC though it waste some memory!
Using h[2500] is not so big wasting of memory as there may be as much as 49*49 different holes in a field. Consider a case as follows:
49 49
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABAB
0 0

### Some more I/O

Posted: Wed Mar 14, 2007 1:05 pm
Input:

Code: Select all

``````5 5
..AAA
E.BBB
..AA.
CC.DD
CC.D.
25 33
.................................
.................................
.................................
.................................
.................................
.................................
....AAAAA.....AAAA.........AAAAA.
......AAAAAAAAAAAAAAAAAAA.AAA.AAA
.....AABBBBBBBBAAAAAA...A.AAA..AA
...AAABAAABBBAAAAAA...AAA..AAA..A
..AABAAA...AAAA.....AAA.....AA..A
.AAABBBBAAAAA.....AAA........A.AA
BBBBBAAAAA.......AAA........AA...
BBBAAAAA........AAA........AAAA..
AAAAAA.........AA.........AAAAAA.
BAAA..........AA.......AAAAABBAA.
BBAAAA.......AA......AAAABBBBBBAA
BBBBAAAA.....AA.....AAABBBBBBBBAA
BBBBBBAAAA...AA....AAABBBBBBBBAAB
AAAAAAAAAA...AAA...AABBBBBBBAAABB
AAAAAAAAAA....AA...AABBAAAAAABBBB
...AAAAAA.....AAA.AAABBBBBBBBBBBB
.....AAA........AA..AAABBBBBBBBBB
....AAA..........AAA..AAAABBBBBBB
AAAAA..............AAAAAAABBBBBBB
5 5
..AAA
E.BBB
..AA.
CC.DD
CC.D.
0 0
``````
Output:

Code: Select all

``````Problem 1:
C 4
A 3
B 3
D 3
A 2
E 1
Problem 2:
A 263
B 76
B 13
B 13
B 11
B 1
5 5
Problem 3:
C 4
A 3
B 3
D 3
A 2
E 1
``````

Posted: Fri Jul 13, 2007 10:32 pm
I got AC after 3 submission. Because i ve calculated the diagonals.

But,
Where is written that diagonals should not be counted?????

???

Posted: Sun Nov 18, 2007 1:58 pm
My prog has passed successfully
all the sample i/o in the board.
But i am getting wa but why?

Code: Select all

``````
//code removed

``````

Thanks.

Posted: Sun Nov 18, 2007 4:17 pm
I have used a queue and used it's size 600
for this I have get wrong ans.
Now I have used size 6000 and get ACC

Thanks everybody

### Re: 10946 - You want what filled?

Posted: Wed Mar 31, 2010 9:54 pm
AC

### Re: 10946 - You want what filled?

Posted: Sun Dec 19, 2010 2:01 pm
HEY......every one.....i am getting bored with my code 0f uav 10946.........not getting AC ....WA each time...
plz some one help me.....my code passed over the test cases posted int tihs forum....and i am also posting my code ....plz some one help me findng the bugs with my code..... tnx in advance

Code: Select all

``````#include<stdio.h>
void flood_it(char x,int i,int j);
char a[55][55];
int s;
struct {
char id;
int fre;
}srt[3000];

int main()
{
int i,j,x,y,r,k,pos;
char c;
k=0;
//	freopen("plz.txt","r",stdin);
while(scanf("%d%d\n",&x,&y)==2&&(x!=0&&y!=0)){
printf("Problem %d:\n",++k);
for(i=1;i<=x;i++){
for(j=1;j<=y;j++)scanf("%c",&a[i][j]);
scanf("\n");
}
r=-1;
for(i=1;i<=x;i++){
for(j=1;j<=y;j++){
if((a[i][j]>64&&a[i][j<91])||(a[i][j]>96&&a[i][j]<123)){
srt[++r].id=a[i][j];
s=0;
flood_it(a[i][j],i,j);
srt[r].fre=s;
}
}
}
for(i=0;i<r;i++){
pos=i;
for(j=i+1;j<=r;j++)if(srt[pos].fre<srt[j].fre)pos=j;
if(i!=pos){
srt[pos].fre=srt[pos].fre+srt[i].fre;
srt[i].fre=srt[pos].fre-srt[i].fre;
srt[pos].fre=srt[pos].fre-srt[i].fre;
c=srt[pos].id;
srt[pos].id=srt[i].id;
srt[i].id=c;
}
}
for(i=0;i<r;i++){
pos=i;
for(j=i+1;j<=r;j++)if(srt[pos].id>srt[j].id)pos=j;
if((i!=pos)&&(srt[pos].fre==srt[i].fre)){
srt[pos].fre=srt[pos].fre+srt[i].fre;
srt[i].fre=srt[pos].fre-srt[i].fre;
srt[pos].fre=srt[pos].fre-srt[i].fre;
c=srt[pos].id;
srt[pos].id=srt[i].id;
srt[i].id=c;
}
}
for(i=0;i<=r;i++){
printf("%c %d\n",srt[i].id,srt[i].fre);
}
}
return 0;
}
void flood_it(char x,int i,int j){
if(a[i][j]!=x)return;
a[i][j]='.';
++s;
flood_it(x,i,j+1);
flood_it(x,i,j-1);
flood_it(x,i+1,j);
flood_it(x,i-1,j);
return;
}``````

### Re: Some more I/O

Posted: Mon Mar 14, 2011 4:46 am
zoranh wrote:Input:

Code: Select all

``````5 5
..AAA
E.BBB
..AA.
CC.DD
CC.D.
25 33
.................................
.................................
.................................
.................................
.................................
.................................
....AAAAA.....AAAA.........AAAAA.
......AAAAAAAAAAAAAAAAAAA.AAA.AAA
.....AABBBBBBBBAAAAAA...A.AAA..AA
...AAABAAABBBAAAAAA...AAA..AAA..A
..AABAAA...AAAA.....AAA.....AA..A
.AAABBBBAAAAA.....AAA........A.AA
BBBBBAAAAA.......AAA........AA...
BBBAAAAA........AAA........AAAA..
AAAAAA.........AA.........AAAAAA.
BAAA..........AA.......AAAAABBAA.
BBAAAA.......AA......AAAABBBBBBAA
BBBBAAAA.....AA.....AAABBBBBBBBAA
BBBBBBAAAA...AA....AAABBBBBBBBAAB
AAAAAAAAAA...AAA...AABBBBBBBAAABB
AAAAAAAAAA....AA...AABBAAAAAABBBB
...AAAAAA.....AAA.AAABBBBBBBBBBBB
.....AAA........AA..AAABBBBBBBBBB
....AAA..........AAA..AAAABBBBBBB
AAAAA..............AAAAAAABBBBBBB
5 5
..AAA
E.BBB
..AA.
CC.DD
CC.D.
0 0
``````
Output:

Code: Select all

``````Problem 1:
C 4
A 3
B 3
D 3
A 2
E 1
Problem 2:
A 263
B 76
B 13
B 13
B 11
B 1
5 5
Problem 3:
C 4
A 3
B 3
D 3
A 2
E 1
``````
I think there is a small error in your output. There should be no "5 5" before "Problem 3:"

Except that, your output is identical to mine.