用了STL的list
,加氧气优化也TLE...
#include <iostream>
#include <cstdio>
#include <list>
using namespace std;
int n, m, cnt, i, j, x, y, node;
list<int> neighbour;
char map[500][500];
int main() {
scanf("%d%d", &n, &m);
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
cin >> map[i][j];
}
}
//BFS最上面一行
for (j = 0; j < m; ++j) {
if (map[0][j] == '0') {
neighbour.push_back(j);
while (neighbour.size()) {
node = neighbour.front();
neighbour.pop_front();
x = node / m;
y = node % m;
//标记已被搜索
map[x][y] = '2';
if (x > 0 && map[x - 1][y] == '0') {
neighbour.push_back((x - 1) * m + y);
}
if (x + 1 < n && map[x + 1][y] == '0') {
neighbour.push_back((x + 1) * m + y);
}
if (y > 0 && map[x][y - 1] == '0') {
neighbour.push_back(x * m + y - 1);
}
if (y + 1 < m && map[x][y + 1] == '0') {
neighbour.push_back(x * m + y + 1);
}
}
}
}
//BFS最下面一行
for (j = 0; j < m; ++j) {
if (map[n - 1][j] == '0') {
neighbour.push_back((n - 1) * m + j);
while (neighbour.size()) {
node = neighbour.front();
neighbour.pop_front();
x = node / m;
y = node % m;
map[x][y] = '2';
if (x > 0 && map[x - 1][y] == '0') {
neighbour.push_back((x - 1) * m + y);
}
if (x + 1 < n && map[x + 1][y] == '0') {
neighbour.push_back((x + 1) * m + y);
}
if (y > 0 && map[x][y - 1] == '0') {
neighbour.push_back(x * m + y - 1);
}
if (y + 1 < m && map[x][y + 1] == '0') {
neighbour.push_back(x * m + y + 1);
}
}
}
}
//最左边
for (i = 0; i < n; ++i) {
if (map[i][0] == '0') {
neighbour.push_back(i * m);
while (neighbour.size()) {
node = neighbour.front();
neighbour.pop_front();
x = node / m;
y = node % m;
map[x][y] = '2';
if (x > 0 && map[x - 1][y] == '0') {
neighbour.push_back((x - 1) * m + y);
}
if (x + 1 < n && map[x + 1][y] == '0') {
neighbour.push_back((x + 1) * m + y);
}
if (y > 0 && map[x][y - 1] == '0') {
neighbour.push_back(x * m + y - 1);
}
if (y + 1 < m && map[x][y + 1] == '0') {
neighbour.push_back(x * m + y + 1);
}
}
}
}
//最右边
for (i = 0; i < n; ++i) {
if (map[i][m - 1] == '0') {
neighbour.push_back(i * m + m - 1);
while (neighbour.size()) {
node = neighbour.front();
neighbour.pop_front();
x = node / m;
y = node % m;
map[x][y] = '2';
if (x > 0 && map[x - 1][y] == '0') {
neighbour.push_back((x - 1) * m + y);
}
if (x + 1 < n && map[x + 1][y] == '0') {
neighbour.push_back((x + 1) * m + y);
}
if (y > 0 && map[x][y - 1] == '0') {
neighbour.push_back(x * m + y - 1);
}
if (y + 1 < m && map[x][y + 1] == '0') {
neighbour.push_back(x * m + y + 1);
}
}
}
}
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
if (map[i][j] == '0') {
++cnt;
}
}
}
printf("%d", cnt);
return 0;
}