大佬求助只有10分
查看原帖
大佬求助只有10分
1267057
aa2211034566楼主2024/3/4 22:09
#include <iostream>
#include <algorithm>
using namespace std;
int n, w, v, sum = 0;
int vist[110][110] = {0};
int a[110][110];
int xx[] = {1, -1, 0, 0};
int yy[] = {0, 0, -1, 1};
int dx, dy;
int check(int x, int y) {
    for (int i = 0; i < 4; i++) {
        dx = x + xx[i];
        dy = y + yy[i];
        while (dx <= n && dy <= n && dx >= 1 && dy >= 1) {
        	if(dx==w&&dy==v) break;//起点不能越过 
            if (vist[dx][dy] == 0 && a[dx][dy] == 0) {
                return 1;//还有可以跳的点 
            }
            dx = dx + xx[i];
            dy = dy + yy[i];
        }
    }
    return -1;
}

void dfs(int x, int y, int ct) {
    if (check(x, y) == -1) {
        sum = max(sum, ct);
        return;
    }
    for (int i = 0; i < 4; i++) {
        dx = x + xx[i];
        dy = y + yy[i];
        while (dx <= n && dy <= n && dx >= 1 && dy >= 1) {
        	if(dx==w&&dy==v) break;
            if (vist[dx][dy] == 0 && a[dx][dy] == 0) {
                vist[dx][dy] = 1;
                ct = ct + abs(dx - x) + abs(dy - y);
                dfs(dx, dy, ct);
                ct = ct - abs(dx - x) - abs(dy - y);
                vist[dx][dy] = 0;
            }
            dx = dx + xx[i];
            dy = dy + yy[i];
        }
    }
}

int main() {
    cin >> n >> w >> v;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    vist[w][v] = 1;
    dfs(w, v, 0);
    cout << sum;
    return 0;
}

2024/3/4 22:09
加载中...