10607 - Siege

hujialie · Post by **hujialie** » Thu Jan 22, 2004 6:10 pm

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 · Post by **horape** » Thu Jan 22, 2004 6:50 pm

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

BBBBB
B   B
B A B
B   B
BBBBB

Saludos,
HoraPe

Adrian Kuegel · Post by **Adrian Kuegel** » Fri Jan 23, 2004 12:23 am

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 · Post by **Dmytro Chernysh** » Fri Jan 23, 2004 12:35 am

Yep Adrian. Right into the dot

A lot of contestants missed exactlty this moment...

horape · Post by **horape** » Fri Jan 23, 2004 3:37 am

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

Per · Post by **Per** » Fri Jan 23, 2004 8:38 am

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.

subbu · Post by **subbu** » Sat Jan 24, 2004 4:46 am

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 · Post by **junbin** » Sat Jan 24, 2004 6:01 am

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?

Dmytro Chernysh · Post by **Dmytro Chernysh** » Sat Jan 24, 2004 6:07 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...
Hence, the answer is -1.

junbin · Post by **junbin** » Mon Jan 26, 2004 3:19 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...
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 · Post by **Dmytro Chernysh** » Mon Jan 26, 2004 3:30 am

Why -1?

The answer is 1. Everything is clear....

hujialie · Post by **hujialie** » Mon Jan 26, 2004 11:08 am

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 · Post by **dwyak** » Thu Mar 18, 2004 6:19 pm

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 · Post by **hujialie** » Sat Mar 20, 2004 4:22 am

Thank you very much for your help, accepted now.

.. · Post by .. » Mon Sep 27, 2004 6:39 pm

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

OJ Board

10607 - Siege

10607 - Siege

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

still WA