WA求求大佬看看DFS

P1443 马的遍历

_zhiqi_ @ 2024-07-29 13:26:52

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2;
struct node {
    int step = 0;
    bool lie = 0;
};
node num[N][N];
int sum[8][2]= {{2,1},{2,-1},{-2,-1},{-2,1},{1,2},{1,-2},{-1,2},{1,2}};
int n,m,x,y,h,l;
void dfs(int a,int b) {
    num[a][b].lie = 1;
    for(int i = 0; i < 8; i++) {
        h = a + sum[i][0];
        l = b + sum[i][1];
        if(num[h][l].lie == 0 &&(a >= 1 && b >= 1 && a <= n && b <= m)) {
            num[h][l].step = num[a][b].step + 1;
            dfs(h,l);
        } else {
            return;
        }
    }
}
int main() {
    cin >> n >> m >> x >> y;
    num[x][y].step = 0;
    num[x][y].lie = 1;
    dfs(x,y);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(num[i][j].step == 0 && i != x && j != y) {
                num[i][j].step = -1;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cout << num[i][j].step << ' ';
        }
        cout << endl;
    }
    return 0;
}

by meifan666 @ 2024-07-29 13:36:11

@zhiqi 这题建议用BFS


by wscmh @ 2024-07-29 13:43:34

bfs比较好求最短路类的题目 @zhiqi


by _zhiqi_ @ 2024-07-29 13:46:43

@wscmh 谢谢


by _zhiqi_ @ 2024-07-29 13:47:13

@meifan666 谢谢


by wangzc2012 @ 2024-07-30 12:32:36

建议用BFS,这道题用DFS会TLE。就像我一样


|