HDU 2102 A计划 DFS与BFS两种写法 [搜索]

1.题意：一位公主被困在迷宫里，一位勇士前去营救，迷宫为两层，规模为N*M，迷宫入口为(0,0,0),公主的位置用'P'标记；迷宫内，'.'表示空地，'*'表示墙，特殊的，'#'表示时空传输机，走到这里就会被传输到另一层的相对位置；在迷宫内没走动一步耗时为1，最终求解是否能在T时刻解救到公主；

2.输入输出：第一行C表示C组数据，每一组内N,M,T给出的迷宫规模与时间，接着给出了双层迷宫的内容；若是能找到公主输出"YES",否则"NO"；

3.分析：这里原题意判断是否能在T时刻找到，然而要是写搜索判断有没有"时刻为T且位置为P"的状态，会超时，所以直接判断能不能在T时刻之前就找到；

BFS版：求出到达P处的最短时间并判断是否小于T；DFS版：找到第一个"时刻小于T且位置为P的状态"就返回；

 # include <iostream>

 # include <cstdio>

 # include <queue>

 # include <cstring>

 using namespace std;

 const int maxn=;

 int N,M,T;

 int dx[]={,,-,};

 int dy[]={-,,,};

 char maze[][maxn][maxn];

 int vis[][maxn][maxn];

 struct Node

 {

     int l,x,y,t;

     Node(){}

     Node(int ll,int xx,int yy,int tt)

     {

         l=ll;

         x=xx;

         y=yy;

         t=tt;

     }

 };

 void Init()

 {

     scanf("%d%d%d",&N,&M,&T);

     for(int i=;i<;i++)

         for(int j=;j<N;j++)

             scanf("%s",maze[i][j]);

     memset(vis,,sizeof(vis));

 }

 void Solve()

 {

     int ans=-;

     queue<Node> Q;

     vis[][][]=;

     Q.push(Node(,,,));

     while(!Q.empty())

     {

         Node temp=Q.front();

         Q.pop();

         if(temp.t<=T&&maze[temp.l][temp.x][temp.y]=='P')

         {

             ans=;

             break;

         }

         if(temp.t>T) break;

         for(int i=;i<;i++)

         {

             int nx=temp.x+dx[i];

             int ny=temp.y+dy[i];

             if(nx>=&&ny>=&&nx<N&&ny<M&&maze[temp.l][nx][ny]!='*'&&!vis[temp.l][nx][ny])

             {

                 if(maze[temp.l][nx][ny]!='#')//"."

                 {

                     vis[temp.l][nx][ny]=;

                     Q.push(Node(temp.l,nx,ny,temp.t+));

                 }

                 else//'#'

                 {

                     vis[temp.l][nx][ny]=vis[!temp.l][nx][ny]=;

                     if(maze[!temp.l][nx][ny]!='*'&&maze[!temp.l][nx][ny]!='#')

                         Q.push(Node(!temp.l,nx,ny,temp.t+));

                 }

             }

         }

     }

     if(ans>) printf("YES\n");

     else printf("NO\n");

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     int C;

     scanf("%d",&C);

     while(C--)

     {

         Init();

         Solve();

     }

     return ;

 }

 # include <iostream>

 # include <cstdio>

 # include <cstring>

 # include <cstdlib>

 using namespace std;

 const int MAXN=;

 char Maze[][MAXN][MAXN];

 int dx[]={,-,,};

 int dy[]={,,,-};

 int vis[][MAXN][MAXN];

 int N,M,T,f;

 void Init()

 {

     f=;

     scanf("%d%d%d",&N,&M,&T);

     for(int k=;k<;k++)

         for(int i=;i<N;i++)

             scanf("%s",Maze[k][i]);

     memset(vis,,sizeof(vis));

 }

 void dfs(int k,int x,int y,int t)

 {

     if(f) return;

     if(t<T&&Maze[k][x][y]=='P')

     {

         f=;

         return;

     }

     if(t==T)

     {

         if(Maze[k][x][y]=='P')

             f=;

         return;

     }

     for(int i=;i<;i++)

     {

         int nx=x+dx[i];

         int ny=y+dy[i];

         if(nx>=&&ny>=&&nx<N&&ny<M&&Maze[k][nx][ny]!='*')

         {

             if(Maze[k][nx][ny]!='#'&&!vis[k][nx][ny])

             {

                 vis[k][nx][ny]=;

                 dfs(k,nx,ny,t+);

                 vis[k][nx][ny]=;

             }

             else

             {

                 if(Maze[!k][nx][ny]!='#'&&Maze[!k][nx][ny]!='*')

                     if(!vis[k][nx][ny]&&!vis[!k][nx][ny])

                     {

                         vis[!k][nx][ny]=vis[k][nx][ny]=;

                         dfs(!k,nx,ny,t+);

                         vis[!k][nx][ny]=vis[k][nx][ny]=;

                     }

             }

         }

     }

 }

 void Solve()

 {

     dfs(,,,);

     if(f) printf("YES\n");

     else printf("NO\n");

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     int C;

     scanf("%d",&C);

     while(C--)

     {

         Init();

         Solve();

     }

     return ;

 }

巴特西

HDU 2102 A计划 DFS与BFS两种写法 [搜索]

最新文章

热门文章