It takes two (搜索)

原创已于 2024-03-27 10:25:38 修改 · 粉丝可见 · 372 阅读 · 4 · 7 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/137069078

本题链接：登录—专业IT笔试面试备考平台_牛客网

题目：

样例：

`cobol<br/>3 4<br/>AAAO<br/>AAAA<br/>AAAA<br/>`

NO

思路：

根据题目意思，如果存在的 A 联通不可以成为矩形，输出 NO，否则输出 YES

这道题看数据范围是 1000 的图，所以可以联想到搜索。

对于 ‘ 感染类’ 的搜索，BFS最直观合适。

其中一个核心点就是如何知道右下角的坐标。

当搜索寻找矩形的时候，我们找到相应的右下角坐标，随后统计搜索的面积与右下角坐标和左上角坐标相乘的面积，是否一致，如果一致，则是矩形，反之。

我们可以注意到，右下角的坐标永远比坐上角的坐标大，即右下角(x,y) > 左上角(x,y)

所以我们每次取坐标的最大值即可。

1
2
3

      // 寻找右下角
lx = max(lx,now.x);
ly = max(ly,now.y);

代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define x first
#define y second
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
inline void solve();
signed main()
{
//	freopen("a.txt", "r", stdin);
	IOS;
	int _t = 1;
// 	cin >> _t;
	while (_t--)
	{
		solve();
	}
 
	return 0;
}
 
bool st[1010][1010];
string g[N];
int n,m;
using PII = pair<int,int>;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
 
// 判断是否可进一步搜索
inline bool isRun(int x,int y)
{
	return (x >= 0 and x < n and y >= 0 and y < m and !st[x][y] and g[x][y] == 'A');
} 
 
// BFS 搜索
inline bool BFS(int x,int y)
{
	queue<PII>q;
	q.emplace(PII(x,y));
	
	int sum = 0; // 记录搜索面积
	
	int lx = -1,ly = -1;	// 记录右下角坐标
	
	while(q.size())
	{
		PII now = q.front();
		q.pop();
		++sum;	// 统计搜索到的面积
		
		// 寻找右下角
		lx = max(lx,now.x);
		ly = max(ly,now.y);
		
		st[now.x][now.y] = true;
		for(int i = 0;i < 4;++i)
		{
			int bx = now.x + dx[i];
			int by = now.y + dy[i];
			if(isRun(bx,by))
			{
				q.emplace(PII(bx,by));
				st[bx][by] = true;
			}
		}
	}
	
	// 计算右下角坐标和左上角坐标形成的矩形面积
	int t = (lx - x + 1)*(ly - y + 1);
	
	// 判断是否与搜索面积相等
	return (t != sum);
}
 
inline void solve()
{
	cin >> n >> m;
	for(int i = 0;i < n;++i) cin >> g[i];
	
	for(int i = 0;i < n;++i)
	{
		for(int j = 0;j < m;++j)
		{
			if(!st[i][j] and g[i][j] == 'A')
			{
				if(BFS(i,j))
				{
					cout << "NO" << endl;
					return ;
				}
			}
		}
	}
	cout << "YES" << endl;
}