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;
}
}
}
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();
}
}
}
