poj_3984_迷宫问题(深搜)
程序员文章站
2022-05-20 20:49:09
...
迷宫问题
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 29580 | Accepted: 17017 |
Description
定义一个二维数组:
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
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
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
Sample Output
(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)
Source
题目大意:
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,
不能斜着走,要求编程序找出从左上角到右下角的最短路线。
简单的模板题,就是要记录路径上经过的点,输出点。只要用个数组记录就可以了。
代码:
c++:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int e[6][6];
int book[6][6];
int a[100],b[100];
int next[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int minx = 999999,step;
struct node
{
int x,y;
};
node path[100];
void dfs(int x,int y,int step)
{
if( x == 4 && y == 4)
{
if(step <= minx)
{
minx = step;
for(int i=1;i<=minx;i++)
{
path[i].x = a[i]; //记录一下路径中的点,路径小的
path[i].y = b[i];
}
}
return ;
}
for(int i=0;i<4;i++)
{
int tx = x+next[i][0];
int ty = y+next[i][1];
if(tx < 0 ||tx >= 5 || ty < 0 || ty >= 5)
continue;
if(book[tx][ty] == 0 && e[tx][ty] == 0)
{
a[step] = tx;
b[step] = ty;
book[tx][ty] = 1;
dfs(tx,ty,step+1);
book[tx][ty] = 0;
}
}
return ;
}
int main()
{
int n = 5;
path[0].x = 0;
path[0].y = 0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
scanf("%d",&e[i][j]);
}
dfs(0,0,1);
//printf("%d\n",minx);
for(int i=0;i<minx;i++)
{
printf("(%d, %d)\n",path[i].x,path[i].y);
}
return 0;
}
Java:
注意Java“结构体”的用法,在Java中不叫结构体,是类。
import java.util.*;
class node
{
int x;
int y;
}
public class Main{
static int e[][] = new int[6][6];
static int book[][] = new int [6][6];
static int a[] = new int[100];
static int b[] = new int[100];
static node path[] = new node[100]; //先声明
static int minx = 999999;
static int next[][] = {{-1,0},{0,1},{1,0},{0,-1}};
public static void dfs(int xx,int yy,int step) {
if(xx == 4 && yy == 4)
{
if(step < minx)
{
minx = step;
for(int i=1;i<=minx;i++)
{
path[i].x = a[i];
path[i].y = b[i];
}
return ;
}
}
for(int i=0;i<4;i++)
{
int tx = xx+next[i][0];
int ty = yy+next[i][1];
if(tx<0 || tx>=5 || ty<0 || ty>=5)
continue;
if(book[tx][ty] == 0 && e[tx][ty] == 0 )
{
a[step] = tx;
b[step] = ty;
book[tx][ty] = 1;
dfs(tx,ty,step+1);
book[tx][ty] = 0;
}
}
return ;
}
public static void main(String [] args) {
Scanner in = new Scanner(System.in);
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
e[i][j] = in.nextInt();
}
for(int i=0;i<100;i++)
path[i] = new node();
path[0].x = 0;
path[0].y = 0;
dfs(0,0,1);
for(int i=0;i<minx;i++)
System.out.println("("+path[i].x+", "+path[i].y+")");
}
}
上一篇: POJ-1321棋盘问题(dfs)
下一篇: SPOJ - PT07Z (DFS)