题号1255

定义一个二维数组：

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

题解(DFS)

#include<iostream>
#include<algorithm>
#include<cstring>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;

const int N = 6;
int g[N][N], dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}, cnt = 1e5;
bool st[N][N];
PII p[30], path[30];


void dfs(int x, int y, int u)
{
    //如果当前的步数已经大于当前的最优解直接返回 
    if(u > cnt) return;
    //到达终点 
    if(x == 4 && y == 4) {
        cnt = min(u, cnt);
        //更新一下路径 
        for(int i = 0; i < cnt; i++)
            path[i] = {p[i].x, p[i].y};
        return;
    }
    //向四个方向进行搜索 
    for(int i = 0; i < 4; i++) {
        int a = x + dir[i][0], b = y + dir[i][1];
        if(a >= 0 && a < 5 && b >= 0 && b < 5 && g[a][b] == 0 && !st[a][b]) {
            st[a][b] = true;
            p[u].x = a, p[u].y = b;
            dfs(a, b, u + 1);
            st[a][b] = false;
        } 
    }
}
int main()
{
    for(int i = 0; i < 5; i++)
        for(int j = 0; j < 5; j++)
            cin >> g[i][j];
    st[0][0] = true;
    dfs(0, 0, 1);
    //输出路径 
    for(int i = 0; i < cnt; i++)
        cout << "(" << path[i].x << ", " << path[i].y << ")" << endl;

    return 0;
}

题解(BFS)

2024-5-3 to