Untitled

 avatar
unknown
plain_text
a month ago
2.0 kB
5
Indexable
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;
using dta = struct {
    int x;
    int y;
    int depth;
};

vector<vector<int>> map(1000);
vector<vector<int>> values(1000);

int main(void) {
    int n, m;
    scanf("%d %d ", &n, &m);
    char inp;
    int aX = 0, aY = 0;
    int bX = 0, bY = 0;
    for (int i = 0; i < n; i++) {
        map[i].resize(1000);
        values[i].resize(1000, __INT32_MAX__);
        for (int j = 0; j < m; j++) {
            scanf("%c", &inp);
            map[i][j] = (inp == '#')?1:0;
            if (inp == 'A') {
                aX = j;
                aY = i;
            } else if (inp == 'B') {
                bX = j;
                bY = i;
            }
        }
        scanf("%*c");
    }

    queue<dta> q;
    q.push((dta){aX, aY, 0});
    while (!q.empty()) {
        dta obj = q.front();
        q.pop();

        if (obj.depth > values[obj.y][obj.x]) {
            continue;
        }
        
        if (obj.y-1 >= 0 && values[obj.y-1][obj.x] > (obj.depth + map[obj.y-1][obj.x])) {
            values[obj.y-1][obj.x] = obj.depth + map[obj.y-1][obj.x];
            q.push((dta){obj.x, obj.y-1, values[obj.y-1][obj.x]});
        }
        if (obj.y+1 < n && values[obj.y+1][obj.x] > (obj.depth + map[obj.y+1][obj.x])) {
            values[obj.y+1][obj.x] = obj.depth + map[obj.y+1][obj.x];
            q.push((dta){obj.x, obj.y+1, values[obj.y+1][obj.x]});
        }
        if (obj.x-1 >= 0 && values[obj.y][obj.x-1] > (obj.depth + map[obj.y][obj.x-1])) {
            values[obj.y][obj.x-1] = obj.depth + map[obj.y][obj.x-1];
            q.push((dta){obj.x-1, obj.y, values[obj.y][obj.x-1]});
        }
        if (obj.x+1 < n && values[obj.y][obj.x+1] > (obj.depth + map[obj.y][obj.x+1])) {
            values[obj.y][obj.x+1] = obj.depth + map[obj.y][obj.x+1];
            q.push((dta){obj.x+1, obj.y, values[obj.y][obj.x+1]});
        }
    }
    printf("%d", values[bY][bX]);

    return 0;
}
Editor is loading...
Leave a Comment