286 - Dead Or Not -- That Is The Question

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

Moderator: Board moderators

Palomar
New poster
Posts: 2
Joined: Thu Nov 21, 2002 3:35 am

problem 286: A question

Post by Palomar » Thu Nov 21, 2002 3:50 am

I'm not sure I understand how the board is laid out.

Take the input:
Kbbbbbbbtlttttttbbbbbbbbssssssssbbbbbbbbllllllllbbbbbbbbtsldklst

This means that K is in a1, b at a2, ... and the last t at h8?

And Isn't the upper left corner at a8? This does not seem to be a normal chess board...

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

286

Post by Caesum » Wed Nov 26, 2003 7:49 pm

Is the third example wrong ?

I mean:
Kqnqqbrnrnqpqrbnrnnrqprqkrrpbqqnbqbbnqqbrprnpppnbrnrnqrbbbnpbbbr

so the corner of the board is:

rnq
Kq

so the K is attacked by q and r, the nearest q is protecting the r and n and the other q protects the first q. So how can this be 'game is not over' ?

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Wed Nov 26, 2003 9:02 pm

Sorry. There was a mistake in the output file. So the sample input and output will be changed. Try solving again. Again sorry.
_____________
NO sigNature

paladin
New poster
Posts: 2
Joined: Sun Dec 07, 2003 10:57 pm

286 - promotion

Post by paladin » Sun Dec 07, 2003 11:15 pm

When a pawn is in the 8th row, do I have to count it as any potentially promoted piece? For example:

K p <-- 8th row
<-- 7th row
k <-- 6th row

Is it a "checkmate", or "game is not over"?

And other question: could anyone supply a tricky test case for this problem? My program gets WA and I cannot catch the mistake, despite long testing.

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

Post by Adrian Kuegel » Mon Dec 08, 2003 12:54 am

No, you can assume that potential promotion already took place.
I think there is no special tricky test case. If you just count how often each field is attacked, then you only have to check the 8 fields surrounding the black king. If there is at least one field which is not attacked (note that each figure doesn't attack the place where it stands), then the king can move, else if it is in check -> game over, else draw.

paladin
New poster
Posts: 2
Joined: Sun Dec 07, 2003 10:57 pm

Post by paladin » Mon Dec 08, 2003 1:06 am

Thank you.
Your algorithm is exactly the same I wrote. However, I'm not able to do it without making mistakes :-)

aakash_mandhar
New poster
Posts: 38
Joined: Thu Dec 11, 2003 3:40 pm
Location: Bangalore

286 - Dead Or Not -- That Is The Question

Post by aakash_mandhar » Wed Feb 04, 2004 8:14 pm

Hi guys, I am breaking my head over this simple problem.. The technique i took is to check if the current position is checked and all other 8 positions are checked or cannot move to....

WHat is the error.. I thnk it could be because i choose an empty cell o move to...

Plz help
[cpp]
# include<stdio.h>

char a[10][10];
int r,c;
int fc,fcm,d,no,i,j,cp,cp1,cp2,cp3,cp4,cp5,cp6,cp7,cp8;
char ch;


checker(int i,int j)
{
int x,y;
if(a[i-1][j+1]=='p' || a[i-1][j-1]=='p') return 1;
for(x=i-1;x>0;x--) if(a[x][j]!=' ') {if(a[x][j]=='r' || a[x][j]=='q') return 1; else break;}
for(x=j-1;x>0;x--) if(a[x]!=' ') {if(a[x]=='r' || a[x]=='q') return 1; else break;}
for(x=i+1;x<=8;x++) if(a[x][j]!=' ') {if(a[x][j]=='r' || a[x][j]=='q') return 1; else break;}
for(x=j+1;x<=8;x++) if(a[x]!=' ') {if(a[x]=='r' || a[x]=='q') return 1; else break;}
for(x=i,y=j;x>0 && y>0;x--,y--) if(a[x][y]!=' ') {if(a[x][y]=='b' || a[x][y]=='q') return 1; else break;}
for(x=i,y=j;x<=8 && y>0;x++,y--) if(a[x][y]!=' ') {if(a[x][y]=='b' || a[x][y]=='q') return 1; else break;}
for(x=i,y=j;x>0 && y<=8;x--,y++) if(a[x][y]!=' ') {if(a[x][y]=='b' || a[x][y]=='q') return 1; else break;}
for(x=i,y=j;x<=8 && y<=0;x++,y++) if(a[x][y]!=' ') {if(a[x][y]=='b' || a[x][y]=='q') return 1; else break;}
if(i+2<=8 && j+1<=8 && a[i+2][j+1]=='n') return 1;
if(i+2<=8 && j-1>0 && a[i+2][j-1]=='n') return 1;
if(i-2>0 && j+1<=8 && a[i-2][j+1]=='n') return 1;
if(i-2>0 && j-1>0 && a[i-2][j-1]=='n') return 1;
if(i+1<=8 && j+2<=8 && a[i+1][j+2]=='n') return 1;
if(i+1<=8 && j-2>0 && a[i+1][j-2]=='n') return 1;
if(i-1>0 && j+2<=8 && a[i-1][j+2]=='n') return 1;
if(i-1>0 && j-2>0 && a[i-1][j-2]=='n') return 1;

if(i+1<=8 && j+1<=8 && a[i+1][j+1]=='k') return 1;
if(i+1<=8 && j-1>0 && a[i+1][j-1]=='k') return 1;
if(i-1>0 && j+1<=8 && a[i-1][j+1]=='k') return 1;
if(i-1>0 && j-1>0 && a[i-1][j-1]=='k') return 1;
if(i+1<=8 && a[i+1][j]=='k') return 1;
if(j-1>0 && a[j-1]=='k') return 1;
if(i-1>0 && a[i-1][j]=='k') return 1;
if(j+1>0 && a[j+1]=='k') return 1;

return 0;
}

int main()
{
while(1)
{
fc=0;fcm=0;d=0;no=0;
for(i=1;i<9;i++)
{
for(j=1;j<9;j++)
{
ch=fgetc(stdin);
if(ch==EOF) return 1;
if(ch=='K') {r=i;c=j;}
a[j]=ch;
/*//printf("%c",ch);*/
}
/*//printf("\n");*/
}
cp=checker(r,c);
/*cp1=1;if(a[r][c+1]==' ') cp1=checker(r,c+1);
cp2=1;if(a[r][c-1]==' ') cp2=checker(r,c-1);
cp3=1;if(a[r+1][c]==' ') cp3=checker(r+1,c);
cp4=1;if(a[r-1][c]==' ') cp4=checker(r-1,c);
cp5=1;if(a[r+1][c+1]==' ') cp5=checker(r+1,c+1);
cp6=1;if(a[r+1][c-1]==' ') cp6=checker(r+1,c-1);
cp7=1;if(a[r-1][c+1]==' ') cp7=checker(r-1,c+1);
cp8=1;if(a[r-1][c-1]==' ') cp8=checker(r-1,c-1);
*/
if(c+1<=8) cp1=checker(r,c+1); else cp1=1;
if(c-1>0) cp2=checker(r,c-1); else cp2=1;
if(r+1<9) cp3=checker(r+1,c); else cp3=1;
if(r-1>0) cp4=checker(r-1,c); else cp4=1;
if(r+1<9 && c+1<9) cp5=checker(r+1,c+1); else cp5=1;
if(r+1<9 && c-1>0) cp6=checker(r+1,c-1); else cp6=1;
if(r-1>0 && c+1<9) cp7=checker(r-1,c+1); else cp7=1;
if(r-1>0 && c-1>0) cp8=checker(r-1,c-1); else cp8=1;

/*//printf("%d %d %d %d %d %d %d %d %d\n",cp,cp1,cp2,cp3,cp4,cp5,cp6,cp7,cp8);*/
if(cp && cp1 && cp2 && cp3 && cp4 && cp5 && cp6 && cp7 && cp8) printf("checkermate\n");
else if(!cp && cp1 && cp2 && cp3 && cp4 && cp5 && cp6 && cp7 && cp8) printf("draw\n");
else printf("game is not over\n");
fgetc(stdin);
}

}
[/cpp]

Thx a (million^miliion+1)

Aakash
...I was born to code...

Delf
New poster
Posts: 3
Joined: Wed Feb 11, 2004 12:02 pm
Contact:

Post by Delf » Wed Feb 11, 2004 12:05 pm

I cannot find my mistakes. Write, please, any tests.

Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:

Post by Aleksandrs Saveljevs » Wed Feb 11, 2004 1:11 pm

Probably, the most common mistake in the problem, which the most obvious way of implementation entails, is that if the king is attacked by something else than a knight or a pawn, make sure it cannot step back, I mean, this position, for instance, is mate: Kc6, Qg8, Kc8.

Delf
New poster
Posts: 3
Joined: Wed Feb 11, 2004 12:02 pm
Contact:

Post by Delf » Wed Feb 11, 2004 1:48 pm

Aleksandrs Saveljevs wrote:Probably, the most common mistake in the problem, which the most obvious way of implementation entails, is that if the king is attacked by something else than a knight or a pawn, make sure it cannot step back, I mean, this position, for instance, is mate: Kc6, Qg8, Kc8.
Thank you, very much!! I got AC :)

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Sat Jun 24, 2006 4:06 pm

Hi,

Yes, you are correct. Input is given in the order, rank 1, rank2 , rank3 ...

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Post by RC's » Sun Jul 15, 2007 6:14 am

any other case ?
I'm still getting WA.

mars kaseijin
New poster
Posts: 22
Joined: Mon Sep 19, 2005 4:58 am
Contact:

Post by mars kaseijin » Mon Dec 17, 2007 5:34 pm

Here is a favourite test case that i use in the early stage.

K r b

mars kaseijin
New poster
Posts: 22
Joined: Mon Sep 19, 2005 4:58 am
Contact:

Post by mars kaseijin » Mon Dec 17, 2007 5:37 pm

woops, electronic board posting ate whitespaces that is meant to be empty squares. :(
any way, here is what i meant:
"K r b"

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

286 - Dead Or Not

Post by x140l31 » Wed Dec 26, 2007 1:15 am

The Input of the problem says
EOF indicates the end of the input file.
What does it mean?

The Input example there's not any "EOF"

Anyone can explain it to me?




Sorry if my english is so bad xD

Post Reply

Return to “Volume 2 (200-299)”