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

走迷宫输出路径 - 题解

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 20;
int a[N][N];
bool st[N][N];
vector<PII> rec;
int n, m;
int xStart, xEnd, yStart, yEnd;
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
int cnt;

void dfs(int x, int y, int k) {
    rec[k].first = x;
    rec[k].second = y;
    if (x == xEnd && y == yEnd) {
        cnt++;
        for (int i = 1; i < k; i++) 
            printf("(%d,%d)->", rec[i].first, rec[i].second);
        printf("(%d,%d)\n", rec[k].first, rec[k].second);
        return;
    }

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m){
        	if (!st[nx][ny] && a[nx][ny] == 1) {
            st[nx][ny] = true;
            dfs(nx, ny, k + 1);
            st[nx][ny] = false;
        	}
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    cin >> xStart >> yStart >> xEnd >> yEnd;
    st[xStart][yStart] = true;
    rec.resize(n * m + 1);
    dfs(xStart, yStart, 1);
    if (cnt == 0) cout << "-1" << endl;
    return 0;
}
0 回复 0 转发 0 喜欢 5 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!