简单dfs：UVA 260 Il Gioco dell'X
写程序果然是要静心，不然就漏洞百出。一道简单的dfs竟然wa了好多次。题解：必有一胜，所以只判断black胜不胜就够了。black胜利的条件是能从第一行走到最后一行，white的胜利条件是能出第一列走到最后一列，要注意的是不（i，j）不能到
(i+1,j-1)和（i-1,j+1）。
#include <iostream>
#include <cstdio>
using namespace std;
int n;
char str;
int ax;
bool flag=true;
int counter=1;
int dir={{-1,-1},{-1,0},{0,-1},{0,1},{1,0},{1,1}};
void dfs(int x,int y){
int dx,dy;
str='.';
for(int i=0;i<6;i++){
dx=x+dir;
dy=y+dir;
if(dx<n && dy<n && dx>=0 && dy>=0&& str=='b'){
ax=dx;
if(ax==n-1){
flag=false;
}
dfs(dx,dy);
}
}
}
int main()
{
while(~scanf("%d",&n)){
flag=true;
if(n==0)break;
ax=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf(" %c",&str);
}
}
for(int i=0;i<n;i++){
if(str=='b'){
dfs(0,i);
}
}
if(flag){
printf("%d W\n",counter);
counter++;
}
else{
printf("%d B\n",counter);
counter++;
}
}
return 0;
}
页:
[1]