hdu 1728 提交总是wa
链接：http://acm.hdu.edu.cn/showproblem.php?pid=1728
先dfs

import java.util.*;
class Node
{
int x,y,dir,turns;
public Node(int x,int y){this.x=x;this.y=y;dir=-1;turns=-1;}
}
public class Main  
{  
static int t,n,m,k,x1,y1,x2,y2,turns;
static char map[][]=new char[101][101];
static int visit[][]=new int[101][101];
static int coor[][]={{0,1},{1,0},{0,-1},{-1,0}};
static boolean flag=false;
static boolean dfs(Node node1,Node node2)
{
if(flag)  return flag;//尽快结束。  ps：不知道有没有起到效果
if(node1.x==node2.x&&node1.y==node2.y&&node1.turns<=k)
{
System.out.println("yes");
flag=true;
}
else
{
for(int i=0;i<4;i++)
{

if(node1.turns>k) break;
if(node1.turns==k&&node1.x!=node2.x&&node1.y!=node2.y)break;//如果已经相等，不在同一行同一列，则跳出
int x=node1.x+coor[i][0];
int y=node1.y+coor[i][1];
Node node=new Node(x,y);
node.dir=node1.dir;
node.turns=node1.turns;
if(node.x<1||node.x>m||node.y<1||node.y>n||map[x][y]=='*'||visit[x][y]==1)
continue;//在界外或者是墙
if(node1.dir!=i){node.dir=i;node.turns=node1.turns+1;}//
System.out.println("X:"+node.x+"Y:"+node.y+"T:"+node.turns);
visit[node.x][node.y]=1;//标记已走过
dfs(node,node2);
visit[node.x][node.y]=0;//恢复标记
}
}
return flag;
}
public static void main(String args[])
{
Scanner cin=new Scanner(System.in);
int num=cin.nextInt();
while(num!=0)
{
num--;
m=cin.nextInt();
n=cin.nextInt();
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
map[i][j]=cin.next().charAt(0);
k=cin.nextInt();
y1=cin.nextInt();
x1=cin.nextInt();
y2=cin.nextInt();
x2=cin.nextInt();
if(x1==x2&&y1==y2)
{
System.out.println("yes");
continue;
}
Node node1=new Node(x1,y1);
Node node2=new Node(x2,y2);
visit[1][1]=1;
if(!dfs(node1,node2))
System.out.println("no");
flag=false;
}
}
}

模仿的bfs也是wa，无语了。

import java.util.*;
class Node
{
int x,y,dir,step;
public Node(int x,int y){this.x=x;this.y=y;}
}
public class Main  
{  
static char map[][]=new char[102][102];
static int visit[][]=new int[102][102];
static int XX[][]={{1,0},{-1,0},{0,1},{0,-1}};
static int m,n,step,x1,y1,x2,y2;
static void bfs()
{
Queue<Node>queue=new LinkedList<Node>();
Node t=new Node(x1,y1);t.dir=-1;
visit[x1][y1]=0;
queue.offer(t);
while(!queue.isEmpty())
{
t=queue.poll();
for(int k=0;k<4;k++)
{
Node tt=new Node(0,0);
tt.x=t.x+XX[k][0];
tt.y=t.y+XX[k][1];
tt.dir=t.dir;
tt.step=t.step;
if(tt.x<1||tt.x>m||tt.y<1||tt.y>n||map[tt.x][tt.y]=='*')
continue;
if(t.dir!=k&&t.dir!=-1)tt.step=t.step+1;
if(tt.step>step)
continue;
if(tt.x==x2&&tt.y==y2)
{
System.out.println("yes");
return;
}
if(visit[tt.x][tt.y]>=tt.step)
{
tt.dir=k; 
 
visit[tt.x][tt.y]=tt.step;
queue.offer(tt);
}
}
}
System.out.println("no");
}
public static void main(String args[])
{
Scanner cin=new Scanner(System.in);
int num=cin.nextInt();
while(num!=0)
{
num--;
m=cin.nextInt();
n=cin.nextInt();
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
map[i][j]=cin.next().charAt(0);
visit[i][j]=999;
}
step=cin.nextInt();
y1=cin.nextInt();
x1=cin.nextInt();
y2=cin.nextInt();
x2=cin.nextInt();
if(x1==x2&&y1==y2)
{
System.out.println("yes");
continue;
}
bfs();
}
}
}

帮我找到bug，不胜感激。
[解决办法]
visit[1][1]=1;改成 visit[x1][y1]=1;
感觉改不改性质都一样，因为返回原点会导致方向改变不会造成死循环，对结果没有影响
[解决办法]
lz说一下自己的思路吧，这个问题不难，bfs应该可以轻松搞定。
没看你的程序，1楼的意思应该是最初可以走到的那两条直线，应该只用了0次转弯。
[解决办法]
>先给你丢个板砖。
3L丢回来了。不多说了。

>我写的dfs，bfs都已经考虑到这个情况了。
你没有。你扩展节点的时候，一个节点扩出去是3个点step+1、1个点step不变，如果没有用优先队列的话，那就不能保证每次取的点step都是单调递增的。你现在相当于有一个边权可以取0/1的图，但你就当它是个边权都是1的图来遍历。这肯定是有问题的。

>dfs只要搜到目标点同时满足转弯次数小于等于k
ok。再看了一遍代码，你的dfs是用不着这个假设的，所以除了visit[1][1]=1这问题以外我暂时找不到其他问题了。顺便debug输出别忘记删掉。

另外bfs里还发现一个问题。999够大么。