10607 - Siege

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10607 - Siege

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

User avatar
horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

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

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

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
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

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

User avatar
horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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
New poster
Posts: 28
Joined: Fri May 30, 2003 12:47 am

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
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

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
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

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
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

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
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Mon Jan 26, 2004 3:30 am

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

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

still WA

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;
}
Retired from SJTU Accelerator 2004

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

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

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

Post by hujialie » Sat Mar 20, 2004 4:22 am

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

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

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
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Post Reply

Return to “Volume 106 (10600-10699)”