UC知道acm杭电1175
来源：百度知道 编辑：UC知道 时间：2024/06/17 07:37:58
大虾们，为什么老是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;
最简单的方法：深度优先搜索！（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,