## 10607 - Siege

Moderator: Board moderators

### 10607 - Siege

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).
Retired from SJTU Accelerator 2004
hujialie
New poster

Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

### Re: 10607---Siege WA,any trick in this problem?

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:

Code: Select all
`BBBBBB   BB A BB   BBBBBB`

Saludos,
HoraPe

horape
New poster

Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

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.
Guru

Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Yep Adrian. Right into the dot A lot of contestants missed exactlty this moment...
Dmytro Chernysh
Experienced poster

Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

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

horape
New poster

Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

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.
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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.
subbu
New poster

Posts: 28
Joined: Fri May 30, 2003 12:47 am

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?
junbin
Experienced poster

Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

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...
Dmytro Chernysh
Experienced poster

Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

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...

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.
junbin
Experienced poster

Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Why -1? The answer is 1. Everything is clear....
Dmytro Chernysh
Experienced poster

Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

### still WA

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;}`
Retired from SJTU Accelerator 2004
hujialie
New poster

Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

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.
Wenyuan Dai, Shanghai Jiaotong University.
dwyak
New poster

Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China

Thank you very much for your help, accepted now.
Retired from SJTU Accelerator 2004
hujialie
New poster

Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

Could anyone give me the output? Thanks

Code: Select all
`5  5BBBBBB   BB A BB   BBBBBB5  5AAAAAA   AA   AA   AAAAAA5  5AAAAAA   AA B AA   AAAAAA5  5AAAAAAB BAABBBAABBBAAAAAA3 3AAAAAAAAA3 3AAAAAAAAB5 6              AA              5 6BBBBBZB    ZB A  ZB    Z33333Z5 6BBBBBZB    ZB  AZZB    Z33333Z5 6       CCCB  CAbb  DDDb       5 6       CCCB  CAbb    Db       0 0`
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.
..
A great helper

Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Next