ACM 廣搜 Hero In Maze

2019-11-11 03:31:48

字體：大中小

來源：轉載

供稿：網友

這是Hero In Maze三道題，分別是TOJ中Hero In Maze簡單版，普通版，提高版。以下我將一一闡述。TOJ 2777 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");    }}