题目描述

题目链接
m×n的迷宫,1表示可走，0表示不可走;
行走优先顺序：左上右下

样例

输入#1
5 6
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
1 1
5 6
------------------------------------------------------------------------------------
输出#1
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)

算法bfs

C++ 代码

#define _CRT_SECURE_NO_WARNINGS 1  
#include <iostream>  
#include <vector>  
#include <queue> 
#include<cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 20;
bool flag = false;
int n, m, sx, sy, ex, ey;
int map[N][N];//地图
bool vis[N][N];//记录有没有走过
int dx[] = { 0, -1, 0, 1 };
int dy[] = { -1, 0, 1, 0 };//方向：左上右下
void dfs(int x, int y, vector<PII>& p) {//下面基本为模板,背诵！！！
    p.push_back({ x,y });
    if (x == ex && y == ey) {
        flag = 1;//flag用于记录是否走到终点
        int sz = p.size();
        for (int i = 0; i < sz; i++) {
            cout << '(' << p[i].first << ',' << p[i].second << ')';
            if (i < sz - 1)cout << "->";
        }
        cout << endl;
    }
    else {
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx > 0 && nx <= n && ny > 0 && ny <= m && !vis[nx][ny] && map[nx][ny] == 1) {
                vis[nx][ny] = true;
                dfs(nx, ny, p);
                vis[nx][ny] = false;//回溯取消标记
            }
        }
    }
    p.pop_back();//回溯阶段
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)cin >> map[i][j];
    cin >> sx >> sy >> ex >> ey;
    memset(vis, false, sizeof(vis));
    vector<PII> p;
    vis[sx][sy] = true;//对起点进行标记(不写会报错)
    dfs(sx, sy, p);
    if (!flag)cout << -1;


    return 0;
}