PKU 1647 One-move checkmate
http://poj.org/problem?id=1647
1手でチェックメイトするようにクイーンを動かせという問題。
シミュレーションしました。
最初キングが王手になっているかを判定していなくてWAをもらいました。
WA地獄になるかと思いましたが、そうでもなくて安心しました。
bool can[8][8]; bool che[8][8]; main(){ string a,b,c; cin>>a>>b>>c; rep(i,8){ int cx=b[0]-'a',cy=b[1]-'1'; while(true){ cx+=dx[i]; cy+=dy[i]; if(min(cx,cy)<0 || max(cx,cy)>=8 || (cx==a[0]-'a' && cy==a[1]-'1'))break; can[cx][cy]=true; } } rep(i,8)rep(j,8){ if(!can[i][j])continue; memset(che,0,sizeof(che)); rep(k,8){ int cx=i,cy=j; int nx=a[0]-'a'+dx[k],ny=a[1]-'1'+dy[k]; if(min(nx,ny)>=0 && max(nx,ny)<8) che[nx][ny]=true; while(true){ cx+=dx[k]; cy+=dy[k]; if(min(cx,cy)<0 || max(cx,cy)>=8 || (cx==a[0]-'a' && cy==a[1]-'1'))break; che[cx][cy]=true; } } bool ok=che[c[0]-'a'][c[1]-'1']; rep(k,8){ int nx=c[0]-'a'+dx[k],ny=c[1]-'1'+dy[k]; if(min(nx,ny)>=0 && max(nx,ny)<8 && !che[nx][ny]) ok=false; } if(ok){ cout<<char(i+'a')<<j+1<<endl; return 0; } } cout<<"no"<<endl; }