10607 - Siege

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

[horape]

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

BBBBB
B   B
B A B
B   B
BBBBB


Saludos,
HoraPe

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

[Dmytro Chernysh]

Yep Adrian. Right into the dot A lot of contestants missed exactlty this moment...

[horape]

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

[Per]

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.

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

[junbin]

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?

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

[junbin]

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.

[Dmytro Chernysh]

Why -1? The answer is 1. Everything is clear....

[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;
}

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

[hujialie]

Thank you very much for your help, accepted now.

[..]

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