286 - Dead Or Not -- That Is The Question

[Palomar]

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]

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]

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

[paladin]

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]

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]

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

[aakash_mandhar]

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

[Delf]

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

[Aleksandrs Saveljevs]

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]

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]

Hi,

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

[RC's]

any other case ?
I'm still getting WA.

[mars kaseijin]

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

K r b

[mars kaseijin]

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

[x140l31]

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