求助
查看原帖
求助
561949
syr1125楼主2023/4/25 20:21
#include <bits/stdc++.h>
using namespace std;

int T, n, m, a[2005][2005], vis[2005][2005], f, dis[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

void dfs(int x, int y)
{	
	for (int i = 0; i < 4; i ++)
	{
		int tx = x + dis[i][0], ty = y + dis[i][1];
		if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && a[tx][ty] == 0)
		{
			f ++;
		}
	}
	for (int i = 0; i < 4; i ++)
	{
		int tx = x + dis[i][0], ty = y + dis[i][1];
		if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && a[tx][ty] == 2 && !vis[tx][ty])
		{
			vis[tx][ty] = 1;
			dfs(tx, ty);
		}
	}
}

int main()
{
	cin >> T;
	while (T --)
	{
		cin >> n >> m;
		for (int i = 1; i <= n; i ++)
		{
			string x;
			cin >> x;
			for (int j = 1; j <= m; j ++)
			{
				if (x[j - 1] == '*') a[i][j] = 1;
			}
		}
		for (int i = 1; i <= n; i ++)
		{
			for (int j = 1; j <= m; j ++)
			{
				if (a[i][j] == 1)
				{
					a[i - 1][j] = (a[i - 1][j] == 1) ? 1 : 2;
					a[i + 1][j] = (a[i + 1][j] == 1) ? 1 : 2;
					a[i][j + 1] = (a[i][j + 1] == 1) ? 1 : 2;
					a[i][j - 1] = (a[i][j - 1] == 1) ? 1 : 2;
				}
			}
		}
		int cnt = 0;
		f = 0;
		for (int i = 1; i <= n; i ++)
		{
			for (int j = 1; j <= m; j ++)
			{
				if (a[i][j] == 2 && !vis[i][j])
				{
					dfs(i, j);
					if (!f) cnt ++;
				}
			}
		}
		if (cnt <= 1) cout << "NO" << endl;
		else cout << "YES" << endl; 
		for (int i = 1; i <= n; i ++)
		{
			for (int j = 1; j <= m; j ++)
			{
				a[i][j] = vis[i][j] = 0;
			} 
		} 
	}
	return 0;
}

2023/4/25 20:21
加载中...