WA球条
查看原帖
WA球条
1058410
Gcc_Gdb_7_8_1楼主2024/12/30 20:22
// Problem: Don't Get Rooked
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/UVA639
// Memory Limit: 0 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)

// clang-format off
#include <bits/stdc++.h>
#ifndef __DEBUG_LIB
#define __DEBUG_LIB

bool isdebug = false;

#define change(x) isdebug = x
#define Debugc \
  if (isdebug) cout
#define Debug if (isdebug)

#endif
using namespace std;

#define LL long long
#define Pii pair<int, int>
#define ULL unsigned long long

namespace gdb7 {
	char ma[6][6];
	int n, ans;
	bool vis[6][6];
	void dfs(int x, int y, int cnt) {
		// cout << x << " " << y << " " << cnt << endl;
		// for (int i = 1; i <= n; ++i) {
			// for (int j = 1; j <= n; ++j) {
				// cout << vis[i][j];
			// }
			// cout << "\n";
		// }
		// cout << "\n";
		if (x == n + 1) {
			ans = max(ans, cnt);
			return ;
		}
		int nx = (x + (y == n)), ny = (y == n) ? 1 : y + 1;
		if (!vis[x][y]) {
			vis[x][y] = true;
			for (int i = 1; ; ++i) {
				if (ma[x + i][y] == 'X') {
					break;
				}
				vis[x + i][y] = true;
			}
			for (int i = 1; ; ++i) {
				if (ma[x - i][y] == 'X') {
					break;
				}
				vis[x - i][y] = true;
			}
			for (int i = 1; ; ++i) {
				if (ma[x][y + i] == 'X') {
					break;
				}
				vis[x][y + i] = true;
			}
			for (int i = 1; ; ++i) {
				if (ma[x][y - i] == 'X') {
					break;
				}
				vis[x][y - i] = true;
			}
			dfs(nx, ny, cnt + 1);
			vis[x][y] = false;
			for (int i = 1; ; ++i) {
				if (ma[x + i][y] == 'X') {
					break;
				}
				vis[x + i][y] = false;
			}
			for (int i = 1; ; ++i) {
				if (ma[x - i][y] == 'X') {
					break;
				}
				vis[x - i][y] = false;
			}
			for (int i = 1; ; ++i) {
				if (ma[x][y + i] == 'X') {
					break;
				}
				vis[x][y + i] = false;
			}
			for (int i = 1; ; ++i) {
				if (ma[x][y - i] == 'X') {
					break;
				}
				vis[x][y - i] = false;
			}
			dfs(nx, ny, cnt);
		} else {
			dfs(nx, ny, cnt);
		}
	}
	int main() {
		while ((~scanf("%d", &n)) && n) {
			memset(vis, 0, sizeof(vis));
			memset(ma, 'X', sizeof(ma));
			for (int i = 1; i <= n; ++i) {
				scanf("%s", ma[i] + 1);
				for (int j = 1; j <= n; ++j) {
					if (ma[i][j] == 'X') {
						vis[i][j] = true;
					}
				}
			}
			ans = 0;
			dfs(1, 1, 0);
			cout << ans << endl;
		}
		return 0;
	}
};  // namespace gdb7

int main() { return gdb7::main(); }

dfs,WA 了,做了两天了555。

2024/12/30 20:22
加载中...