Untitled
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