求调玄关
查看原帖
求调玄关
1036180
ChampionCyan楼主2024/8/12 21:22
#include <bits/stdc++.h>
using namespace std;
bool black[2005][2005];
bool mp[2005][2005];
bool vis[2005][2005];
int n, m;

bool check(int x, int y) {
	if (x < 0 || y < 0 || x > n || y > m)
		return true;
    if (x > 1)
		if (!(black[x - 1][y] || mp[x - 1][y]))
			return true;
	if (y > 1)
		if (!(black[x][y - 1] || mp[x][y - 1]))
			return true;
	if (x < n)
		if (!(black[x + 1][y] || mp[x + 1][y]))
			return true;
	if (y < m)
		if (!(black[x][y + 1] || mp[x][y + 1]))
			return true;
	return false;
}

inline bool bfs(int i, int j) {
	if (vis[i][j])
		return false;
	queue<pair<int, int> > q;
	q.push(make_pair(i, j));
	while (!q.empty()) {
		int x = q.front().first, y = q.front().second;
		q.pop();
		if (x < 0 || y < 0 || x > n || y > m || vis[x][y] || black[x][y] || !mp[x][y])
			continue;
		vis[x][y] = true;
		if (check(x, y))
			return false;
		q.push({x + 1, y}),
		q.push({x - 1, y}),
		q.push({x, y + 1}),
        q.push({x, y - 1});
	}
	return true;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int cnt = 0;
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			string str;
			cin >> str;
			for (int j = 0; j < str.length(); j++)
				black[i][j + 1] = (str[j] == '*');
		}
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				vis[i][j] = false, 
				mp[i][j] = (!black[i][j] && (black[i][j + 1] || black[i][j - 1] || black[i - 1][j] || black[i + 1][j]));
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				if (bfs(i, j))
					cnt++;
		if (cnt < 2)
			puts("YES");
		else
			puts("NO");
	}
	return 0;
}
2024/8/12 21:22
加载中...