차단된 것과 차단되지 않은 두 가지 유형의 셀을 포함하는 h * w 차원의 그리드가 제공된다고 가정합니다. 차단된 셀은 셀에 액세스할 수 없음을 의미하고 차단 해제는 셀에 액세스할 수 있음을 의미합니다. 차단된 셀은 '#'으로 표시되고 차단되지 않은 셀은 '.'로 표시되는 2D 배열로 그리드를 나타냅니다. 이제 우리는 차단되지 않은 셀에서 그리드의 차단되지 않은 다른 셀로 도달해야 합니다. 우리는 두 가지 움직임만 수행할 수 있습니다. 수직으로 이동하거나 수평으로 이동할 수 있습니다. 우리는 대각선으로 이동할 수 없습니다. 우리는 차단되지 않은 세포로만 이동할 수 있음을 명심해야 합니다. 따라서 그리드의 다른 차단되지 않은 셀에서 차단되지 않은 셀에 도달하는 데 필요한 최대 이동 횟수를 찾아야 합니다.
따라서 입력이 h =4, w =4, grid ={"..#.", "#.#.", "..##", "###."}인 경우 출력은 4가 됩니다.
셀(0,0)에서 셀(2,0)에 도달하려면 최대 4번의 이동이 필요합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
Define an array xdir of size: 4 := {1, 0, - 1, 0} Define an array ydir of size: 4 := {0, 1, 0, - 1} Define one 2D array dist Define one 2D array reset res := 0 for initialize i := 0, when i < h, update (increase i by 1), do: for initialize j := 0, when j < w, update (increase j by 1), do: dist := reset if grid[i, j] is same as '.', then: dist[i, j] := 0 Define one queue q containing integer pairs insert make_pair(i, j) into q while (not q is empty), do: x := first element of the leftmost element in the q y := second element of the leftmost element in the q res := maximum of (dist[x, y] and res) delete leftmost element from q for initialize k := 0, when k < 4, update (increase k by 1), do: px := x + xdir[k] py := y + ydir[k] if px >= 0 and px < h and py >= 0 and py < w, then: if grid[px, py] is same as '.', then: if dist[px, py] is same as -1, then: dist[px, py] := dist[x, y] + 1 insert pair(px, py) into q return res에 삽입합니다.
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h> using namespace std; int solve(int h, int w, vector<string> grid){ int xdir[4] = {1, 0, -1, 0}; int ydir[4] = {0, 1, 0, -1}; vector<vector<int>> dist(h, vector<int>(w, -1)); vector<vector<int>> reset(h, vector<int>(w, -1)); int res = 0; for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ dist = reset; if(grid[i][j] == '.'){ dist[i][j] = 0; queue<pair<int,int>> q; q.push(make_pair(i, j)); while(!q.empty()){ int x = q.front().first; int y = q.front().second; res = max(dist[x][y], res); q.pop(); for(int k = 0; k < 4; k++){ int px = x + xdir[k]; int py = y + ydir[k]; if(px >= 0 && px < h && py >= 0 && py < w){ if(grid[px][py] == '.'){ if(dist[px][py] == -1){ dist[px][py] = dist[x][y] + 1; q.push(make_pair(px, py)); } } } } } } } } return res; } int main() { int h = 4, w = 4; vector<string> grid = {"..#.", "#.#.", "..##", "###."}; cout << solve(h, w, grid); return 0; }
입력
4, 4, {"..#.", "#.#.", "..##", "###."}
출력
4