poj 3984:迷宫问题（广搜，入门题）

迷宫问题

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 7635		Accepted: 4474

Description

定义一个二维数组：

int maze[5][5] = {

	0, 1, 0, 0, 0,

	0, 1, 0, 1, 0,

	0, 0, 0, 0, 0,

	0, 1, 1, 1, 0,

	0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

Sample Output

(0, 0)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)

Source

　　广搜，入门题。

　　题意：

　　给你一个5*5的迷宫，0代表通路，1代表墙，找到从迷宫左上角到达右下角的最短路径，并输出路径。

　　思路：

　　这道题是一道比较简单的广搜题目，为什么是广搜？因为题意是要找最短路径，这类题基本上就是用广搜。但是与其他直接输出最短路径的步数的不同，这道题要输出的是最短路径，是要输出这个路径，所以就要考虑状态了，每一个状态都应该存储到达这个状态的路径。其他就没什么好说的了，总体上是一道较为简单的广搜入门题。

　　代码：

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <queue>

 using namespace std;

 bool isw[][];

 int a[][];

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

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

 struct Node{

     int x;

     int y;

     int s;

     short l[];

 };

 bool judge(int x,int y)

 {

     if(x< || x>= || y< || y>=)

         return true;

     if(isw[x][y])

         return true;

     if(a[x][y]==)

         return true;

     return false;

 }

 Node bfs()

 {

     queue <Node> q;

     Node cur,next;

     cur.x = ;

     cur.y = ;

     cur.s = ;

     isw[cur.x][cur.y] = true;

     q.push(cur);

     while(!q.empty()){

         cur = q.front();

         q.pop();

         if(cur.x== && cur.y==)

             return cur;

         int i,nx,ny;

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

             nx = cur.x + dx[i];

             ny = cur.y + dy[i];

             if(judge(nx,ny))

                 continue;

             //可以走

             next = cur;

             next.x = nx;

             next.y = ny;

             next.s = cur.s + ;

             next.l[cur.s] = i;

             q.push(next);

         }

     }

     return cur;

 }

 int main()

 {

      int i,j;

     for(i=;i<;i++){   //读入迷宫

         for(j=;j<;j++){

             scanf("%d",&a[i][j]);

         }

     }

     memset(isw,,sizeof(isw));

     Node ans = bfs();

     int x,y;

     x = ,y = ;

     for(i=;i<=ans.s;i++){

          printf("(%d, %d)\n",x,y);

          x+=dx[ans.l[i]];

          y+=dy[ans.l[i]];

     }

     return ;

 }

Freecode : www.cnblogs.com/yym2013

秒客网

poj 3984:迷宫问题（广搜，入门题）

相关文章