Walls and Gates
問題概要
https://gyazo.com/507732fa082971824c961db21f2c059f
2Dの地図が与られるので、スタート地点である0地点からのそれぞれのマスへの最短歩数を求め、与えられた二次元配列を書き換えよ、という問題
-1は壁で通れない
解法
当初DFSで解こうとしたがRuntime Errorになったりそもそも計算量が$ O(m^2n^2)でTLEになる BFSでqueueを使うやり方だとokなようなので実装し直した 以下のやり方なら(一度通ったマスは計算しないので)計算量はO(mn)
今考えればこれはBFSの典型問題だったnixii.icon code:solution.cpp
using pos = pair<int, int>;
class Solution {
public:
// y and x position
vector<pos> dir = {p(1, 0), p(-1, 0), p(0, 1), p(0, -1)};
void wallsAndGates(vector<vector<int>>& rooms) {
int m = rooms.size();
if (m < 1) return;
queue<pos> q;
for (int y=0; y<m; y++) for (int x=0; x<n; x++) if (roomsyx == 0) q.push(p(y, x)); while (q.size() > 0) {
pos cur_pos = q.front();
q.pop();
for (pos d : dir) {
int y = cur_pos.first + d.first;
int x = cur_pos.second + d.second;
// INT_MAXコマと-1コマも探索先から除外
if (y < 0 || m <= y || x < 0 || n <= x || roomsyx != INT_MAX) continue; // queueのデータ構造によりスタート地点に近い方からroomsyxを更新できるので、 // 最小値を取るみたいなことは必要ない
q.push(p(y, x));
}
}
}
pos p(int a, int b) { return make_pair(a, b); }
};
/icons/-.icon
以下はDFSで解こうとしたがなぜかRuntime Errorになったコード
原因は未特定
code:runtime_error_dfs.cpp
using pos = pair<int, int>;
class Solution {
public:
vector<vector<int>> maze;
void wallsAndGates(vector<vector<int>>& rooms) {
maze = rooms;
vector<pos> starts = {};
for (int i=0; i<maze.size(); i++) {
for (int j=0; j<maze0.size(); j++) { if (mazeij == 0) starts.push_back(make_pair(i, j)); }
}
for (pos s : starts) {
vector<pos> visited = {};
traverse(s, 1, visited);
}
}
void traverse(pos start, int path_score, vector<pos> visited) {
if (!check_pos(start, visited)) return;
visited.push_back(start);
// up and down, left and right
vector<pos> dir = {p(0, 1), p(0, -1), p(1, 0), p(-1, 0)};
for (int i=0; i<4; i++) {
pos new_pos = make_pair(start.first+diri.first, start.second+diri.second); traverse(new_pos, path_score+1, visited);
}
}
pos p(int x, int y) { return make_pair(x, y); }
bool check_pos(pos start, vector<pos> visited) {
if (start.first < 0 || maze0.size() <= start.first) return false; if (start.second < 0 || maze.size() <= start.first) return false;
if (find(visited.begin(), visited.end(), start) != visited.end()) return false;
return true;
}
};