BFS就行了。提交了好几次TLE,找不到原因,开一个O2,竟然AC了。。。
有同样情况或者觉得因缺思厅的XD请点个赞!
算法1
(BFS+枚举障碍物的上下左右格子即可) $O(nm)$
时间复杂度
O(nm)
参考文献
C++ 代码
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e9;
const int N = 1010;
int n, m;
char g[N][N], c[N][N];
int st[N][N], id[N][N];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
vector<pii>v;
unordered_map<int, int>sum;
bool go(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m;
}
int bfs(int x, int y, int val) {
queue<pii>q;
q.push({x, y});
st[x][y] = 1;
int cnt = 0;
while(q.size()) {
auto t = q.front();
q.pop();
x = t.first; y = t.second;
cnt++;
id[x][y] = val;
for(int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if(go(nx, ny) && !st[nx][ny] && g[nx][ny] == '.') {
st[nx][ny] = 1;
q.push({nx, ny});
}
}
}
return cnt;
}
int calc(int x, int y) {
set<int>s;
int res = 0;
for(int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if(go(nx, ny) && g[nx][ny] == '.' && !s.count(id[nx][ny])) {
s.insert(id[nx][ny]);
res += sum[id[nx][ny]];
}
}
return res;
}
int main(int argc, char * argv[])
{
scanf("%d%d", &n, &m);
v.clear();
sum.clear();
for(int i = 0; i < n; i++){
scanf("%s", g[i]);
for(int j = 0; j < m; j++) {
if(g[i][j] == '*')
v.push_back({i, j});
c[i][j] = g[i][j];
}
}
memset(st, 0, sizeof st);
int k = 1;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++) {
if(g[i][j] == '.' && !st[i][j]) {
int cnt = bfs(i, j, k);
sum[k++] = cnt;
// cout << i << ' ' << j << ' ' << cnt << endl;
}
}
}
for(auto a: v) {
int x = a.first, y = a.second;
int t = (calc(x, y) + 1) % 10;
c[x][y] = t + '0';
}
for(int i = 0; i < n; i++)
printf("%s\n", c[i]);
return 0;
}
哪一行啊,为什么我的不行
第一行,写法不一样的情况就不清楚了
我没加这行也ac了【捂脸】
wc,ac了,谢谢佬
客气了
牛,我打完这行也过了
妙吧
我也是。。
给力吧
哈哈我比赛的时候是忘记取模了。。一直wa哈哈
大佬请问 O(2)啥意思啊?
O2优化