ACM 广搜 Hero In Maze

描述

500年前，Jesse是我国最卓越的剑客。他英俊潇洒，而且机智过人^_^。

突然有一天，Jesse心爱的公主被魔王困在了一个巨大的迷宫中。Jesse听说这个消息已经是两天以后了，他急忙赶到迷宫，开始到处寻找公主的下落。

请你判断他是否能救出心爱的公主。(假设有路可以通到公主那就可以找到公主)。

输入

题目包括多组测试数据。每组测试数据以两个整数n,m(0<n, m≤20)开头，分别代表迷宫的长和高。紧接着有m行，n列字符，由"."，"*"，"P"，"S"组成。其中 "." 代表能够行走的空地。 "*" 代表墙壁，Jesse不能从此通过。 "P" 是公主所在的位置。 "S" 是Jesse的起始位置。 Jesse只能选择上、下、左、右任意一方向走一步。 输入以0 0结束。

输出

如果能救出公主输出YES，否则输出NO。

样例输入

4 4............S**P4 4........****S**P0 0

样例输出

YESNO

这个用深搜就可以，直接判断能不能从S走到P即可。

#include <stdio.h>int a,b,s,k=0;char m[21][21];	int dir[4][2]={1,0,0,1,-1,0,0,-1};void dfs(int x,int y){     if(m[x][y]=='P')   k=1;	m[x][y]='*';	int i,xx,yy;   for(i=0;i<4;i++)   {   	xx=x+dir[i][0];   	yy=y+dir[i][1];   	if(xx>=0&&xx<a&&yy>=0&&yy<b&&m[xx][yy]!='*')    dfs(xx,yy);   }	}int main()//2777{	int i,j,u,w;	while(scanf("%d%d",&a,&b))	{   	    s=0;k=0;		if(a==0&&b==0)break;					for(i=0;i<a;i++)		{getchar();			for(j=0;j<b;j++)			{				scanf("%c",&m[i][j]);			   if(m[i][j]=='S')			    u=i,w=j;			}		} 		dfs(u,w);		if(k==0)		PRintf("NO/n");		else		printf("YES/n");	}}
TOJ 1005 Hero In Maze
描述
500年前，Jesse是我国最卓越的剑客。他英俊潇洒，而且机智过人^_^。突然有一天，Jesse心爱的公主被魔王困在了一个巨大的迷宫中。Jesse听说这个消息已经是两天以后了，他知道公主在迷宫中还能坚持T天，他急忙赶到迷宫，开始到处寻找公主的下落。时间一点一点的过去，Jesse还是无法找到公主。最后当他找到公主的时候，美丽的公主已经死了。从此Jesse郁郁寡欢，茶饭不思，一年后追随公主而去了。T_T500年后的今天，Jesse托梦给你，希望你帮他判断一下当年他是否有机会在给定的时间内找到公主。他会为你提供迷宫的地图以及所剩的时间T。请你判断他是否能救出心爱的公主。
输入
题目包括多组测试数据。每组测试数据以三个整数N,M,T(0<n, m≤20, t>0)开头，分别代表迷宫的长和高，以及公主能坚持的天数。紧接着有M行，N列字符，由"."，"*"，"P"，"S"组成。其中"." 代表能够行走的空地。"*" 代表墙壁，Jesse不能从此通过。"P" 是公主所在的位置。"S" 是Jesse的起始位置。每个时间段里Jesse只能选择“上、下、左、右”任意一方向走一步。输入以0 0 0结束。
输出
如果能在规定时间内救出公主输出“YES”，否则输出“NO”。
样例输入
4 4 10............S**P0 0 0
样例输出
YES
题目意思与上面一致，但是这题要判断时间，所以不能用深搜了，需要用广搜来计算最短时间。
这是一个大佬写的，我没看懂...
http://blog.csdn.net/j_sure/article/details/19997869
#include <cstdio>  #include <iostream>  #include <algorithm>  #include <cstring>   #include <queue>  using namespace std;   int DTx[4]={-1,0,1,0};  int DTy[4]={0,1,0,-1};  char map[25][25];  int dp[25][25];  int x,y,X,Y;  int minn;  int n,m,t;  struct H{      int x,y;      int time;  };  int bfs(int h,int z)  {      int i,j;      queue <H> q;      H a,b,c;      a.x=h;      a.y=z;      a.time=0;      q.push(a);      while(!q.empty())      {          b=q.front();          q.pop();          if(b.x==X&&b.y==Y)              return b.time;          for(i=0;i<4;i++)          {              c.x=b.x+DTx[i];              c.y=b.y+DTy[i];              if(c.x>=0&&c.x<m&&c.y>=0&&c.y<n&&!dp[c.x][c.y])                  {                      dp[c.x][c.y]=1;                      c.time=b.time+1;                      q.push(c);                  }          }      }      return -1;  }  int main()  {      int i,j;      while(~scanf("%d%d%d",&n,&m,&t)&&(n||m||t))      {          memset(dp,0,sizeof dp);          for(i=0;i<m;i++)              cin>>map[i];          for(i=0;i<m;i++)              for(j=0;j<n;j++)              if(map[i][j]=='S')              {x=i;y=j;dp[i][j]=1;}              else if(map[i][j]=='P')              {X=i;Y=j;}              else if(map[i][j]=='*')                  dp[i][j]=1;          minn=bfs(x,y);           //printf("%d/n",minn);           if(minn<=t&&minn!=-1)          printf("YES/n");          else 	printf("NO/n");      }      return 0;  }  
TOJ 3305 Hero In Maze ||
描述
500年前，Jesse是我国最卓越的剑客。他英俊潇洒，而且机智过人^_^。突然有一天，Jesse心爱的公主被魔王困在了一个巨大的迷宫中。Jesse听说这个消息已经是两天以后了，他急忙赶到迷宫，开始到处寻找公主的下落。令人头痛的是，Jesse是个没什么方向感的人，因此，他在行走过程中，不能转太多弯了，否则他会晕倒的。 我们假定Jesse和公主所在的位置都是空地，初始时，Jesse所面向的方向未定，他可以选择4个方向的任何一个出发，而不算成一次转弯。希望你帮他判断一下他是否有机会找到心爱的公主。 
输入
题目包括多组测试数据.
第1行为一个整数T(1 ≤ T≤ 100),表示测试数据的个数，接下来为T组测试数据.
每组测试数据以两个整数N,M,K(1<=N, M≤100, 0<K<=10)开头，分别代表迷宫的高，长和Jesse最多能转的弯数，(紧接着有N行，M列字符，由"."，"*"，"P"，"S"组成。其中"." 代表能够行走的空地。 "*" 代表墙壁，Jesse不能从此通过。 "P" 是公主所在的位置。 "S" 是Jesse的起始位置。 每个时间段里Jesse只能选择“上、下、左、右”任意一方向走一步。 
输出
如果Jesse能在晕之前找到公主，输出“YES”，否则输出“NO”。
样例输入
25 5 1P..***.**.S.........*....5 5 2P..***.**.S.........*....
样例输出
NOYES
题目意思与上一致，就是判断条件从时间变成了转弯次数。注意初始的一次不算转弯。
判断转弯次数的话我设置了一个wan,即第一次转的方向（i）和第二次的不一样时，就是转弯了。
然后我写的广搜TOJ没AC，但是我感觉完美了...先放上来吧~
#include <cstdio>  #include <iostream>  #include <algorithm>  #include <cstring>  #include <cmath>  #include <queue>using namespace std;   int DTx[4]={-1,0,1,0};  int DTy[4]={0,1,0,-1};  char map[101][101];  int dp[101][101];  int x,y,X,Y;  int minn;  int n,m,t;  struct H{      int x,y;      int time,wan;  };  int bfs(int h,int z)  {      int i,j;      queue <H> q;      H a,b,c;      a.x=h;      a.y=z;      a.time=-1; 	a.wan=-1;     q.push(a);      while(!q.empty())      {          b=q.front();          q.pop();          if(b.x==X&&b.y==Y)              return b.time;          for(i=0;i<4;i++)          {              c.x=b.x+DTx[i];              c.y=b.y+DTy[i];              c.wan=i;            if(c.x>=0&&c.x<m&&c.y>=0&&c.y<n&&!dp[c.x][c.y])                  {                      dp[c.x][c.y]=1;                      if(c.wan!=b.wan)//若两次方向一样，则没有转弯。                     c.time=b.time+1; 					q.push(c);                 }          }      }      return -1;  }  int main()  {      int i,j,o;      scanf("%d",&o);    while(o--)      {  		scanf("%d%d%d",&m,&n,&t);         memset(dp,0,sizeof dp);          for(i=0;i<m;i++)              cin>>map[i];          for(i=0;i<m;i++)              for(j=0;j<n;j++)              if(map[i][j]=='S')              {x=i;y=j;dp[i][j]=1;}              else if(map[i][j]=='P')              {X=i;Y=j;}              else if(map[i][j]=='*')                  dp[i][j]=1;          minn=bfs(x,y);           //printf("%d/n",minn);           if(minn<=t&&minn!=-1)          printf("YES/n");          else 		printf("NO/n");      }      return 0;  }  
然后下面的是童冰学姐写的深搜，简单很多。
#include<stdio.h>int n,m,b[4][2]={{0,1},{0,-1},{1,0},{-1,0}},s,k;char a[101][101];void dfs(int x,int y,int r,int w){    if(k==1)return;    int i,x0,y0,r0;    if(x<0||y<0||x>=n||y>=m||r>s+1||a[x][y]=='*')return;    if(a[x][y]=='P')	{k=1;return;}    a[x][y]='*';    for(i=0;i<4;i++)    {        x0=x+b[i][0];        y0=y+b[i][1];        if(w!=i)        r0=r+1;        else r0=r;        dfs(x0,y0,r0,i);    }    a[x][y]='.';}int main(){    int i,j,x0,y0,t;    scanf("%d",&t);    while(t--)    {        k=0;        scanf("%d%d%d",&n,&m,&s);        for(i=0;i<n;i++)        {        	scanf("%s",a[i]);        	for(j=0;j<m;j++)        	{            	if(a[i][j]=='S')            	x0=i,y0=j;        	}		}        dfs(x0,y0,0,-1);        if(k)printf("YES/n");        else printf("NO/n");    }}