Page 1 of 2
10607 - Siege
Posted: Thu Jan 22, 2004 6:10 pm
by hujialie
Hello.Is there any trick in this problem?
I try to solve it, but always got wrong answer.
Maybe I haven't understood the problem clearly.
In the problem, there is
the king should do one of these statements: either it is a frontier province or it is an already conquered province.
What does this sentence actually mean?
And,will "-1" be printed out?(as far as I can see, there should
be no case to print -1).
Re: 10607---Siege WA,any trick in this problem?
Posted: Thu Jan 22, 2004 6:50 pm
by horape
hujialie wrote:Hello.Is there any trick in this problem?
I try to solve it, but always got wrong answer.
Maybe I haven't understood the problem clearly.
In the problem, there is
the king should do one of these statements: either it is a frontier province or it is an already conquered province.
What does this sentence actually mean?
And,will "-1" be printed out?(as far as I can see, there should
be no case to print -1).
Yes, problem is tricky. I had 10 WA before solving it.
There can be spaces on the input and they mean "not a province"
Consider:
Saludos,
HoraPe
Posted: Fri Jan 23, 2004 12:23 am
by Adrian Kuegel
Hi,
In my accepted program I would also count a space region
I mean a province marked with space character.
The tricky part is the -1, I missed it during the online contest. Consider following test case:
BBBBB
BAAAB
BACAB
BAAAB
BBBBB
Clearly, C cannot be conquered, but it is adjacent to province A. So A cannot be surrounded, and therefore cannot be conquered, so you have to print -1.
Posted: Fri Jan 23, 2004 12:35 am
by Dmytro Chernysh
Yep Adrian. Right into the dot
A lot of contestants missed exactlty this moment...
Posted: Fri Jan 23, 2004 3:37 am
by horape
Adrian Kuegel wrote:Hi,
In my accepted program I would also count a space region
I mean a province marked with space character.
Then IMHO "All the symbols have ASCII-code higher than 32(blank)." should be changed to "higher than or equal to 32".
Saludos,
HoraPe
Posted: Fri Jan 23, 2004 8:38 am
by Per
horape wrote:Then IMHO "All the symbols have ASCII-code higher than 32(blank)." should be changed to "higher than or equal to 32"
My solution ignores everything with ascii <= 32, so since Adrian's solution includes such regions I would guess there are no inputs such as the one you posted. My guess is that your patch for handling space regions also covers the case that Adrian posted.
Posted: Sat Jan 24, 2004 4:46 am
by subbu
In order to conquer a province, the king should do one of these statements: either it is a frontier province or it is an already conquered province.
Could anybody clarify this statement in the problem..
I am struggling to make sense out of it.
Thx.
Posted: Sat Jan 24, 2004 6:01 am
by junbin
Adrian Kuegel wrote:Hi,
In my accepted program I would also count a space region
I mean a province marked with space character.
The tricky part is the -1, I missed it during the online contest. Consider following test case:
BBBBB
BAAAB
BACAB
BAAAB
BBBBB
Clearly, C cannot be conquered, but it is adjacent to province A. So A cannot be surrounded, and therefore cannot be conquered, so you have to print -1.
Why can't C be conquered? Is it because of the line saying that he is not strong enough to conquer all the provinces?
Posted: Sat Jan 24, 2004 6:07 am
by Dmytro Chernysh
Simply because C doesn't have boundaries with any other provinces, except A, of course, but A is not a province according to the statement...
Hence, the answer is -1.
Posted: Mon Jan 26, 2004 3:19 am
by junbin
Dmytro Chernysh wrote:Simply because C doesn't have boundaries with any other provinces, except A, of course, but A is not a province according to the statement...
Hence, the answer is -1.
Ooops.. I mistook C for the capital.
What I meant to ask was:
CCC
CAC
CCC
in such a case, would it be -1? Because in the text, there's a line about how he cannot take all the provinces.
Posted: Mon Jan 26, 2004 3:30 am
by Dmytro Chernysh
Why -1?
The answer is 1. Everything is clear....
still WA
Posted: Mon Jan 26, 2004 11:08 am
by hujialie
I have improved my code, considered cases memtioned above,
and I think my programme can handle them, but still received
wrong answer
, can anyone give some tests or point my error?
Thanks.
here is my code in C++:
Code: Select all
#include "stdio.h"
int m,n,p,c[210][210],p2,neigh[101];
char map[210][210];
int cy[4]={0,1,0,-1},cx[4]={1,0,-1,0};
bool link[102][102];
void dfs(int y,int x,int cnum)
{
int i,ty,tx;
c[y][x]=cnum;
for(i=0;i<4;i++)
{
ty=y+cy[i];
tx=x+cx[i];
if(ty>0&&ty<=m&&tx>0&&tx<=n&&c[ty][tx]==0&&map[ty][tx]==map[y][x])dfs(ty,tx,cnum);
}
}
void decidelink(int y,int x)
{
int ty,tx,i;
for(i=0;i<4;i++)
{
ty=y+cy[i];
tx=x+cx[i];
if(ty>0&&ty<=m&&tx>0&&tx<=n)
{
link[c[y][x]][c[ty][tx]]=true;
link[c[ty][tx]][c[y][x]]=true;
}
else
{
link[0][c[y][x]]=true;
link[c[y][x]][0]=true;//frontier province;
}
}
}
void dijkstra()
{
bool visited[101];
int i,j,cur,mid,min[101],best[101];
for(i=1;i<=p;i++)
{
visited[i]=false;
if(link[0][i])min[i]=1;
else min[i]=30000;
}
min[0]=0;//start from frontier;
visited[0]=true;
while(1)
{
cur=30000;
for(j=0;j<=p;j++)
{
if(!visited[j]&&min[j]<cur)
{
cur=min[j];
mid=j;
}
}
if(cur==30000)break;//stop;
best[mid]=cur;
visited[mid]=true;
if(mid!=1)//not inside A;
{
for(j=0;j<=p;j++)
{
if(!visited[j]&&link[mid][j]&&cur+1<min[j])min[j]=cur+1;
}
}
}
for(i=1;i<=p2;i++)if(!visited[neigh[i]])break;
if(i>p2&&visited[1])printf("%d\n",best[1]+p2-2);
else printf("-1\n");;//has an unreachable neighour inside A;
}
int main()
{
char nouse[100];
int i,j;
//freopen("10607.in","r",stdin);
//freopen("10607.out","w",stdout);
while(1)
{
scanf("%d%d",&m,&n);
gets(nouse);
if(m==0&&n==0)break;
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
c[i][j]=0;
scanf("%c",&map[i][j]);
}
gets(nouse);
}
p=1;
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(c[i][j]==0)
{
if(map[i][j]=='A')dfs(i,j,1);//1 stands for capital province;
else
{
if(map[i][j]>32)
{
p++;
dfs(i,j,p);
}
else c[i][j]=101;//illegal char, thus not a country;
}
}
}
}//decide the countries;
for(i=0;i<=p;i++)for(j=0;j<=p;j++)link[i][j]=false;
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{decidelink(i,j);}
}
p2=0;
for(i=2;i<=p;i++)
{
if(link[i][1])
{
p2++;//direct neighbour of capital province;
neigh[p2]=i;
}
}
dijkstra();
}
return 0;
}
Posted: Thu Mar 18, 2004 6:19 pm
by dwyak
first, you shouldn't treat spaces as illegal char.
then, you should modify *all* your array size to 200.
i modified these points in your code, and got AC.
it's not your mistakes. i believe that there are some invalid cases in the judge cases.
Posted: Sat Mar 20, 2004 4:22 am
by hujialie
Thank you very much for your help, accepted now.
Posted: Mon Sep 27, 2004 6:39 pm
by ..
Could anyone give me the output? Thanks
Code: Select all
5 5
BBBBB
B B
B A B
B B
BBBBB
5 5
AAAAA
A A
A A
A A
AAAAA
5 5
AAAAA
A A
A B A
A A
AAAAA
5 5
AAAAA
AB BA
ABBBA
ABBBA
AAAAA
3 3
AAA
AAA
AAA
3 3
AAA
AAA
AAB
5 6
AA
5 6
BBBBBZ
B Z
B A Z
B Z
33333Z
5 6
BBBBBZ
B Z
B AZZ
B Z
33333Z
5 6
CCCB
CAbb
DDDb
5 6
CCCB
CAbb
Db
0 0