本题链接:登录—专业IT笔试面试备考平台_牛客网
题目:
样例:
|
NO |
思路:
根据题目意思,如果存在的 A 联通不可以成为 矩形,输出 NO,否则输出 YES
这道题看数据范围是 1000 的图,所以可以联想到搜索。
对于 ‘ 感染类 ’ 的搜索,BFS最直观合适。
其中一个核心点就是如何知道右下角的坐标。
当搜索寻找矩形的时候,我们找到相应的右下角坐标,随后统计搜索的面积与右下角坐标和左上角坐标相乘的面积,是否一致,如果一致,则是矩形,反之。
我们可以注意到,右下角的坐标永远比坐上角的坐标大,即 右下角(x,y) > 左上角(x,y)
所以我们每次取 坐标的最大值即可。
// 寻找右下角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;
}
最后提交: