Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
37994 | wl2025 | 【S】T2 | C++ | 通过 | 100 | 348 MS | 57792 KB | 1810 | 2025-06-08 15:39:51 |
#include <bits/stdc++.h> using namespace std; const int N = 1005; int n, xx, yy; int a[N][N], b[N][N]; int e[N][N][4]; int vis[N][N], tot, ax[N * N], ay[N * N], d[N][N], ans[N][N]; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; bool init(int x, int y) { vis[x][y] = 1; tot++; ax[tot] = x, ay[tot] = y; if (x == n && y == yy) return 1; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (!e[x][y][i] || vis[nx][ny]) continue; if (init(nx, ny)) return true; } vis[x][y] = 0; tot--; return false; } void dfs(int x, int y, int lim1, int lim2) { for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (!e[x][y][i] || vis[nx][ny]) continue; if (nx < lim1) continue; vis[nx][ny] = 1; if (nx >= lim2) ans[nx][ny] = 2; else ans[nx][ny] = 1; dfs(nx, ny, lim1, lim2); } } void solve() { int mn = n + 1; for (int i = tot; i; i--) { int x = ax[i], y = ay[i]; if (i == tot) d[x][y] = x; else d[x][y] = min(x, d[ax[i + 1]][ay[i + 1]]); ans[x][y] = 1; if (d[x][y] < x) ans[x][y] = 2; if (ans[x][y] == 2) mn = min(mn, x); if (i == tot || (ax[i + 1] == x + 1 && ans[x + 1][y] != 2)) continue; dfs(x, y, d[x][y], min(mn, x + 1)); } } int main() { cin >> n >> xx >> yy; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> a[i][j]; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> b[i][j]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { e[i][j][0] = a[i][j] ^ 1; e[i][j][1] = a[i + 1][j] ^ 1; e[i][j][2] = b[i][j] ^ 1; e[i][j][3] = b[i][j + 1] ^ 1; } } init(1, xx); solve(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) cout << ans[i][j] << ' '; cout << '\n'; } return 0; }