广搜,#7 TLE,求优化建议
查看原帖
广搜,#7 TLE,求优化建议
301200
bac0id楼主2020/11/10 12:01

用了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;
}
2020/11/10 12:01
加载中...