#include <iostream>
#include <string>
#include <stdio.h>
using namespace std; int Map[1001][1001],vis[1001][1001];
int stx,sty,enx,eny,n,m,flag;
int xx,yy,turn,k,i,j;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};//两个数组表示四个方向 void DFS(int x,int y,int turn,int k)//k表示转弯的方向
{
if(flag) return;
if(turn>2)return;
if(turn==2)
{
if(x!=enx&&y!=eny) return; //不在同一直线上
if(x!=enx){ //如果仅仅是列方向上相同，判断当前点和终点的趋势
if(x-enx>0&&k!=1) return;
if(x-enx<0&&k!=0) return;}
if(y!=eny){ //不在同一列上
if(y-eny>0&&k!=3) return;
if(y-eny<0&&k!=2) return;}
//判断如果转了两个弯，
//然后起始点是否朝着终点运动
}
if(turn<=2&&x==enx&&y==eny)
{
flag=1;
return;
} for(i=0;i<4;i++) //四个方向的运动
{
int xx=x+dx[i]; int yy=y+dy[i];
if(!vis[xx][yy]&&(!Map[xx][yy]||(xx==enx&&yy==eny))){//如果没被访问过并且满足1.（此点非0） 2.（已经是终点）两个条件中一个
//说明符合
if(i!=k&&k!=-1) turn++; //所以此时只要判断转的方向i不同于k，既又转了弯，k!=-1只是用来判断第一次
vis[xx][yy]=1;
DFS(xx,yy,turn,i);
vis[xx][yy]=0; //如果回溯回来，要把标记的点还原
if(i!=k&&k!=-1) turn--;
}
}
}
int main()
{
while(scanf("%d%d",&m,&n)&&n||m)
{
for( i = 0; i <= m + 1; i++)
for( j = 0; j <= n + 1; j++)
vis[i][j] = -1; //起初把外围一圈标记为-1
// memset(vis,-1,sizeof(vis));
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&Map[i][j]);
vis[i][j]=0;
}
int T;
scanf("%d",&T);
while(T--)
{
flag=0;
scanf("%d%d%d%d",&stx,&sty,&enx,&eny); //输入起始，终点坐标
if(stx!=enx||sty!=eny) //在起始和终点不同的情况下来判断，不过我觉得貌似是多余的。。。
if(Map[stx][sty]>0&&Map[stx][sty]==Map[enx][eny])//如果坐标大于0，说明不是道路
{
vis[stx][sty]=1;
DFS(stx,sty,0,-1);
vis[stx][sty]=0; //测试数据有好几组吧，所以每次要重新还原
}
if(flag)
printf("YES\n");
else
printf("NO\n");
}
}
return 0;
}
上面的是WA代码
//解题报告
//题目是hdu 1175
//题意大概是一个棋盘，给出起始和终点，然后判断是否能消去，思路很明确，用深搜写
//从题目给出的条件来看，主要在一个转弯问题上和搜索判断的思路上，最后测试数据的时候，都过了，但是提交都WR。。。汗
AC代码:
#include <stdio.h>
#include <string.h>
#define max_size 1005
int num[max_size][max_size], visited[max_size][max_size], index_i, index_j, flag, n, m;
int a[4][2] =
{
1, 0,
-1, 0,
0, 1,
0,-1
};
void dfs(int x, int y, int turn, int index) {
if(flag)
return;
//违背规则的
if(turn > 2)
return;
if(turn == 2) {
//不在同一直线
if(x != index_i && y != index_j)
return;
//在同一列，运动方向不是往目标移动
if(x != index_i)
if(x - index_i > 0 && index != 1 || x - index_i < 0 && index != 0)
return;
//在同一行，运动方向不是往目标移动
if(y != index_j)
if(y - index_j > 0 && index != 3 || y - index_j < 0 && index != 2)
return;
}
//满足条件的
if(turn <= 2 && x == index_i && y == index_j) {
flag = 1;
return;
}
for(int i = 0; i < 4; ++i)
{
int nx = x + a[i][0], ny = y + a[i][1];
if(!visited[nx][ny] && (!num[nx][ny] || nx == index_i && ny == index_j))
{
if(i != index && index != -1)
turn++;
visited[nx][ny] = 1;
dfs(nx, ny, turn, i);
visited[nx][ny] = 0;
if(i != index && index != -1)
turn--;
}
}
}
int main() {
while(scanf("%d%d", &n, &m) && n || m) {
for(int i = 0; i <= n + 1; ++i)
for(int j = 0; j <= m + 1; ++j)
visited[i][j] = -1;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) {
scanf("%d", &num[i][j]);
visited[i][j] = 0;
}
int Q;
scanf("%d", &Q);
while(Q--) {
int start_i, start_j;
scanf("%d%d%d%d", &start_i, &start_j, &index_i, &index_j);
flag = 0;
if(start_i != index_i || start_j != index_j)
if(num[start_i][start_j] == num[index_i][index_j] && num[start_i][start_j] > 0) {
visited[start_i][start_j] = 1;
dfs(start_i, start_j, 0, -1);
visited[start_i][start_j] = 0;
}
if(flag)
printf("YES\n");
else
printf("NO\n");
}
}
}