返回题解分享
讨论 / 题解分享/ 帖子详情

走迷宫输出路径 - 题解

DFS遍历每条路并回溯,用vector存放坐标

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
vector<PII> v;
const int N = 20;
int mp[N][N];
int vis[N][N];
int n,m;
int sx,sy;
int x2,y2;
int dx[] = {0,-1,0,1};
int dy[] = {-1,0,1,0};
int flag = 0;
void dfs(int x,int y){
    vis[x][y] = 1;
    if (x == x2 && y == y2) {
        flag = 1;
        printf("(%d,%d)",sx,sy);
        for (int i = 1; i < v.size() - 1; ++i){
            printf("->(%d,%d)",v[i].first,v[i].second);
        }
        printf("->(%d,%d)\n",x2,y2);
    }
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
        if (vis[nx][ny]) continue;
        if (mp[nx][ny] == 0) continue;
        vis[nx][ny] = 1;
        v.push_back({nx,ny});
        dfs(nx,ny);
        v.pop_back();
        vis[nx][ny] = 0;
    }
    return;
}
int main(){
    scanf("%d %d",&n,&m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> mp[i][j];
        }
    }
    scanf("%d %d",&sx,&sy);
    scanf("%d %d",&x2,&y2);
    v.push_back({sx,sy});
    dfs(sx,sy);
    if(flag == 0) printf("-1\n");
    return 0;
}
0 回复 0 转发 0 喜欢 2 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!