bfs。样例过了,为什么会全wa,求助
  • 板块P1683 入门
  • 楼主leileigwl
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/4/4 10:47
  • 上次更新2023/10/23 19:29:25
查看原帖
bfs。样例过了,为什么会全wa,求助
724584
leileigwl楼主2023/4/4 10:47
#include "cstring"
#include "iostream"
#include "queue"
using namespace std;
typedef pair<int, int> pii;
const int N = 30;
char g[N][N];
int dist[N][N], w, h, res;
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
bool check(pii index) {
    auto t = index;
    if (g[t.first][t.second] == '#' || t.first < 0 || t.first > h ||
        t.second < 0 || t.second > w || dist[t.first][t.second] != -1)
        return false;
    return true;
}
void bfs(pii start) {
    memset(dist, -1, sizeof dist);
    queue<pii> q;
    q.push(start);
    dist[start.first][start.second] = 1;
    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int x = dx[i] + t.first, y = t.second + dy[i];
            if (check({x, y})) {
                q.push({x, y});
                dist[x][y] = dist[t.first][t.second] + 1;
                res = max(dist[x][y], res);
                g[x][y] = '#';
            }
        }
    }
}
int main() {
    // freopen("in.in", "r", stdin);
    cin >> w >> h;
    pii start;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> g[i][j];
            if (g[i][j] == '@')
                start = {i, j};
        }
    }
    bfs(start);
    printf("%d", res);
}

2023/4/4 10:47
加载中...