TOP > グラフ グリッド上の幅優先探索(Grid-BFS) 2018/03/25 • ei1333 説明 二次元格子上の幅優先探索。 計算量 $O(HW)$ 実装例 grid_bfs($s$, $start$, $wall$):= グリッド $s$ 上にある文字 $start$ からすべてのマスへの最短距離を求める。$wall$ には移動できない。到達できるマスには最短距離、できないマスには $-1$ が格納される。 vector< vector< int > > grid_bfs(vector< string > &s, char start, const string &wall = "#") { const int vx[] = {0, 1, 0, -1}, vy[] = {1, 0, -1, 0}; vector< vector< int > > min_cost(s.size(), vector< int >(s[0].size(), -1)); queue< pair< int, int > > que; for(int i = 0; i < s.size(); i++) { for(int j = 0; j < s[i].size(); j++) { if(s[i][j] == start) { que.emplace(i, j); min_cost[i][j] = 0; } } } while(!que.empty()) { auto p = que.front(); que.pop(); for(int i = 0; i < 4; i++) { int ny = p.first + vy[i], nx = p.second + vx[i]; if(nx < 0 || ny < 0 || nx >= s[0].size() || ny >= s.size()) continue; if(min_cost[ny][nx] != -1) continue; if(wall.find(s[ny][nx]) != string::npos) continue; min_cost[ny][nx] = min_cost[p.first][p.second] + 1; que.emplace(ny, nx); } } return min_cost; }