标记数组的位置很重要,一定要放在入队之前,不然会T掉 - 学到了!!!
在bfs中,如果对于之后的某个合法位置,应该入队,那么标记数组会有两种方法,第一种是在每次取队首元素的时候,标记已经遍历过当前点了,还有一种方法是在入队之后就马上标记。之前没太注意这个,但是是完全不一样的,对于8个方向,比如向左走一步是合法的,然后不马上标记的话,例如当前向下和向左都是合法的,那么当向下走时候(比如向下先入队了),那么向左走还会被记录一次,这个很难debug出来,很奇怪的感觉
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const int maxn = 2e3 + 6;
int n, m;
int mp[maxn][maxn];
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
queue<pair<int ,int > >q;
void bfs(int x, int y){
mp[x][y] = 0;
while(q.size()) q.pop();
q.push({x, y});
while(q.size()){
auto now = q.front(); q.pop();
for(int i = 0;i < 8;++i){
int nx = now.first + dx[i];
int ny = now.second + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= m || mp[nx][ny] == 0) continue;
q.push({nx, ny});
mp[nx][ny] = 0;
}
}
}
int main(){
sd(n), sd(m);
for(int i = 0;i < n;++i){
for(int j = 0;j < m;++j){
char c; cin >> c;
if(c == 'W') mp[i][j] = 1;
else mp[i][j] = 0;
}
}
int cnt = 0;
for(int i = 0;i < n;++i){
for(int j = 0;j < m;++j){
if(mp[i][j] == 1){
bfs(i, j);
cnt++;
}
}
}
cout << cnt << endl;
return 0;
}
我也好奇这个问题 ,刚才找了半天呢
请问那个using 重命名和那个输入函数有相关文章吗 可以进一步吗 比如说类似于Java的重写 函数名不变 局部变量变化 ll int char什么的
大佬,按常理说就算我用第一种方式标记,也不应该出现答案错误啊??为什么会呢??
好棒棒啊 ~~