Openjudge 迷宫问题

迷宫问题

总时间限制:
1000ms
内存限制:
65536kB
描述
定义一个二维数组:

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表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。

输入
一个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
样例输出
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int map[7][7];
struct S{
    int x;
    int y;
}step[26];
bool visited[7][7];
int x_arr[5]={0,1,-1,0,0};
int y_arr[5]={0,0,0,1,-1};
int DFS(int x,int y,int step_i,int max){
    if(x<1||x>5||y<1||y>5||map[x][y]==1||visited[x][y])return 30;
    if(x==5&&y==5){
        step[step_i].x=x;
        step[step_i].y=y;
        return step_i;
    }
    visited[x][y]=true;
    int min=30;
    for(int i=1;i<=4;i++){
        int t=DFS(x+x_arr[i],y+y_arr[i],step_i+1,min);
        if(t<min)min=t;
    }
    visited[x][y]=false;
    if(min<30){//从递归的思路上去看,只管当前节点:如果min<30,当前节点就一定是当前路径上的一点,那么要把它加入到当前记录的路径中;如果有比他长的路径,那么短的路径会覆盖长的路径(此处还有问题??但是如果长的路径在短的路径后面,路径记录就会不准确,应该需要max参数,这道题应该是数据弱吧,)
        step[step_i].x=x;
        step[step_i].y=y;
        return min;
    }
    return 30;
}
int main(){
    memset(map,1,sizeof(map));
    memset(visited,false,sizeof(visited));
    for(int i=1;i<=5;i++){
        for(int j=1;j<=5;j++){
            scanf("%d",&map[i][j]);
        }
    }
    int last=DFS(1,1,1,30);
    for(int i=1;i<=last;i++){
        printf("(%d, %d)\n",step[i].x-1,step[i].y-1);
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注