题解
2024-12-06 22:11:30
发布于:广东
67阅读
0回复
0点赞
首先说一句:
这是入门?
这是入门?
这是入门?
本来看了眼题目就直接写广搜
bool bfs(short x, short y){
vector <node> v;
vis[x][y] = 1;
v.push_back({x, y});
for(int i = 0; i < v.size(); i++){
for(int j = 0; j < 4; j++){
short xx = v[i].x + dir[j][0], yy = v[i].y + dir[j][1];
if(check(xx, yy)){
vis[xx][yy] = 1;
v.push_back({xx, yy});
}
}
}
sort(v.begin(), v.end());
int len1 = 0, len2 = 0, idx1 = v[0].x, idx2 = v[v.size() - 1].x;
if(idx2 - idx1 <= 1) return 0;
for(int i = 0; i < v.size(); i++){
if(v[i].x == idx1) len1++;
if(v[i].x == idx2) len2++;
}
if(len1 != len2 || idx2 - idx1 - 1 != v.size() - len1 - len2) return 0;
return 1;
}
结果:我服了怎么还不能C里面套C的
还好,不需要全部改,加一段就行了
接下来就是完整代码:
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct node{
short x, y;//省内存
bool operator < (const node &b) const{//直接重新定义小于好吧
if(x == b.x) return y < b.y;
return x < b.x;
}
};
char mp[2005][2005];
bool vis[2005][2005];
int dir[4][2] = {-1, 0, 0, -1, 0, 1, 1, 0};
int n, m, ct;
bool check(short x, short y){
if(x < 1 || x > n || y < 1 || y > m) return 0;
if(mp[x][y] == '.' || vis[x][y]) return 0;
return 1;
}
bool bfs(short x, short y){
vector <node> v;
vis[x][y] = 1;
v.push_back({x, y});
for(int i = 0; i < v.size(); i++){//广搜,不用queue的原因是还要用一遍数据
for(int j = 0; j < 4; j++){
short xx = v[i].x + dir[j][0], yy = v[i].y + dir[j][1];
if(check(xx, yy)){
vis[xx][yy] = 1;
v.push_back({xx, yy});
}
}
}
sort(v.begin(), v.end());//排个序
short len1 = 0, len2 = 0, idx1 = v[0].x, idx2 = v[v.size() - 1].x, left = v[0].y, right = 0;
if(idx2 - idx1 <= 1) return 0;/*如果idx2-idx1为1的话就是
******
******
这种情况*/
for(int i = 0; i < v.size(); i++){
right = max(right, v[i].y);
if(v[i].x == idx1) len1++;
if(v[i].x == idx2) len2++;
}
if(len1 != len2 || idx2 - idx1 - 1 != v.size() - len1 - len2) return 0;//头尾长度不相等或c里面有字符连在一起
for(int i = idx1 + 1; i < idx2; i++){
for(int j = left + 1; j <= right; j++){
if(mp[i][j] == '*') return 0;//c里面有其他字符但不连在一起
}
}
return 1;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
scanf("%s", mp[i] + 1);
}for(short i = 1; i <= n; i++){
for(short j = 1; j <= m; j++){
if(mp[i][j] == '*' && !vis[i][j]){
ct += bfs(i, j);
}
}
}cout << ct;
return 0;
}
全部评论 1
你这个代码!~正经的?
2024-12-06 来自 江苏
0正经的,本来就有这么难,可以升黄了
2024-12-06 来自 广东
0实际上,这个算法不是正解,因为它的真正时间复杂度为 ,能被轻松hack掉
2024-12-06 来自 广东
0
有帮助,赞一个