Question

acm杭电1175

http://acm.hdu.edu.cn/showproblem.php?pid=1175
大虾们，为什么老是wa哦，真的是郁闷啦。最近做题目老是wa，结果总发现一些小错误，有没有什么好的建议哦！谢谢啦！
#include<iostream>
#include<queue>
using namespace std;
struct node
{
int x,y;
int p;
int turn;
};
queue<node>Q;
node start,now,next;
int num[1001][1001];
int mark[1001][1001];
int n,m,sx,sy,ex,ey,flag;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int bound(int x,int y)
{
if(x>=1 && x<=n && y>=1 && y<=m)
return 1;
return 0;
}
void bfs()
{
int i,nx,ny;
while(!Q.empty())
{
now=Q.front();
Q.pop();
if(flag) return;
if(now.x==ex && now.y==ey && now.p<=2)
{
cout<<"YES"<<endl;
flag=1;
return;
}
if(now.p>2) continue;

for(i=0;i<4;i++)
{
nx=next.x=now.x+dir[i][0];
ny=next.y=now.y+dir[i][1];
if(!bound(nx,ny)) continue;
if(num[nx][ny]) continue;
if(mark[nx][ny]) continue;
if(now.turn!=i)
{
next.p=now.p+1;
next.turn=i;
mark[nx][ny]=1;
}
else
{
next.p=now.p;
next.turn=now.turn;
mark[nx][ny]=1;
}
Q.push(next);
}
}
}
int main()
{
int i,j,k;
while(cin>>n>>m && n+m)
{
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
cin>>num[i][j];
cin>>k;
while(k--)
{
cin>>sx>>sy>>ex>>ey;
memset(mark,0,sizeof(mark));
mark[sx][sy]=1;
flag=0;
if(num[sx][sy]!=num[ex][ey] || !num[sx][sy] || !num[ex][ey] ||(sx==ex && sy==ey))
{
cout<<"NO"<<endl;
continue;
}
while(!Q.empty())
Q.pop();
num[ex][ey]=0;
for(i=0;i<4;i++)
{
start.x=sx;
start.y=sy;
start.p=0;
start.turn=i;
Q.push(start);
}
bfs();
if(!flag)
cout<<"NO"<<endl;
}
}
return 0;
}

Answer 1

最简单的方法：深度优先搜索！（DFS）
不需要很复杂的算法的！！
一次就AC的。WA的话注意以下几点就可以了：
1、两个格子是否相同，不同直接 NO
2、是否有个格子是0， 有的话直接 NO
3、两个格子的位置是否重合，是的话直接 NO
4、运算DFS，找到一个可用路径就直接 YES

#include <iostream>
using namespace std;

enum DIRECTION
{
UP,
RIGHT,
DOWN,
LEFT,
STAY
};

bool dfs(const int*const* map,DIRECTION D,int x,int y,const int d_x,const int d_y,int turns,const int b_x,const int b_y)
{
if(turns==3) return false; //如果转过3次了,直接就False
if(x<0||x==b_x||y<0||y==b_y) return false;//如果超过的边界,直接False
if(x==d_x&&y==d_y&&turns<3) return true;//如果到达目的格子,返回True
if(D!=STAY&&map[x][y]!=0) return false;//如果遇到不是0的格子,就直接False,开始的格子除外
switch(D) //对方向进行分类
{
case UP: //目前方向向上
if(dfs(map,UP,x-1,y,d_x,d_y,turns,b_x,b_y)) return true; //原方向
if(dfs(map,LEFT,x,y-1,d_x,d_y,turns+1,b_x,b_y)) return true; //往左,转向+1
if(dfs(map,RIGHT,x,y+1,d_x,d_y,turns+1,b_x,b_y)) return true; //往右,转向+1
break;
case LEFT: //目前方向向左
if(dfs(map,LEFT,x,y-1,d_x,d_y,turns,b_x,b_y)) return true; //原方向
if(dfs(map,UP,x-1,y,d_x,d_y,turns+1,b_x,b_y)) return true; //往上,转向+1
if(dfs(map,DOWN,x+1,y,d_x,d_y,turns+1,b_x,b_y)) return true; //往下,转向+1
break;
case RIGHT: //目前方向向右
if(dfs(map,RIGHT,x,y+1,d_x,d_y,turns,b_x,b_y)) return true; //原方向
if(dfs(map,UP,x-1,y,d_x,d_y,turns+1,b_x,b_y)) return true; //往上,转向+1
if(dfs(map,DOWN,x+1,y,d_x,d_y,turns+1,b_x,b_y)) return true; //往下,转向+1
break;
case DOWN: //目前方向向下
if(dfs(map,DOWN,x+1,y,d_x,d_y,turns,b_x,b_y)) return true; //原方向
if(dfs(map,LEFT,x,y-1,d_x,d_y,turns+1,b_x,b_y)) return true; //往左,转向+1
if(dfs(map,RIGHT,x,y+1,d_x,d_y,turns+1,b_x,b_y)) return true; //往右,转向+1
break;
case STAY: //目前是初始位置
if(dfs(map,UP,x-1,y,d_x,d_y,turns,b_x,b_y)) return true; //往上
if(dfs(map,DOWN,x+1,y,d_x,d_y,turns,b_x,b_y)) return true; //往下
if(dfs(map,LEFT,x,y-1,d_x,d_y,turns,b_x,b_y)) return true; //往左
if(dfs(map,RIGHT,x,y+1,d_x,d_y,turns,b_x,b_y)) return true; //往右
break;
}
return false;
}

int main()
{
int n,m;
while(cin >> n >> m)
{
if(n==0||m==0) break;
int** map = new int*[n];
for(int i=0;i<n;i++)
{
map[i] = new int[m];
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin >> map[i][j];
}
}
int q;
cin >> q;
while(q--)
{
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
if(x1==x2&&y1==y2) //两个重合直接 NO
{
cout << "NO\n";
continue;
}
if(map[x1-1][y1-1]!=map[x2-1][y2-1]||map[x1-1][y1-1]==0) //两格不一样或者有一个是0直接 NO
{
cout << "NO\n";
continue;
}
if(dfs(map,STAY,x1-1,y1-1,x2-1,y2-1,0,n,m)) cout << "YES\n"; //找到一个路径就 YES
else cout << "NO\n"; //找不到就 NO
}
}
}

Run ID: 1622424
Submit Time: 2009-08-18 03:22:57
Judge Status: Accepted
Pro. ID: 1175
Exe. Time: 4421MS
Exe. Memory: 1316K
Code Len.: 2217 B
Language: C++
Author: Parker