차단된 것과 차단되지 않은 두 가지 유형의 셀을 포함하는 x * y 차원의 그리드가 제공된다고 가정합니다. 차단된 셀은 셀에 액세스할 수 없음을 의미하고 차단 해제는 셀에 액세스할 수 있음을 의미합니다. 차단된 셀은 '#'으로 표시되고 차단되지 않은 셀은 '.'로 표시되는 2D 배열로 그리드를 나타냅니다. 이제 셀(0, 0)에서 셀(x, y)까지 도달해야 합니다. 우리는 두 가지 이동만 수행할 수 있습니다. 세포 오른쪽으로 이동하거나 세포에서 아래로 이동할 수 있습니다. 우리는 차단되지 않은 셀에만 들어갈 수 있으며 (0, 0)과 (x, y)는 모두 차단되지 않은 셀이라는 것을 명심해야 합니다. (0, 0)에서 (x, y)에 도달할 수 없으면 차단된 셀을 차단되지 않은 셀로 만들 수 있습니다. 소스에서 목적지에 도달하기 위해 수행할 변경 작업의 최소 수를 찾아야 합니다.
따라서 입력이 x =4, y =4, grid ={"..#.", "#.#.", "#.##", "###."}인 경우 출력은 1이 됩니다.
한 번의 변경 작업만 수행하면 됩니다. 셀(2, 2)을 차단됨에서 차단되지 않음으로 변경하면 (0, 0)에서 (3, 3)에 도달할 수 있습니다.
단계
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
Define one 2D array mat
if grid[0, 0] is same as '#', then:
mat[0, 0] := 1
Otherwise
mat[0, 0] := 0
for initialize i := 0, when i < x, update (increase i by 1), do:
for initialize j := 0, when j < y, update (increase j by 1), do:
if i + 1 < x, then:
mat[i + 1, j] = minimum of (mat[i + 1, j], mat[i, j] + (1 if grid[i + 1, j] is same as '#' AND grid[i, j] is same as '.'))
if j + 1 < y, then:
mat[i, j + 1] = minimum of (mat[i, j + 1], mat[i, j]+(1 if grid[i, j + 1] is same as '#' AND grid[i, j] is same as '.'))
return mat[x - 1, y - 1] 예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
int solve(int x, int y, vector<string> grid){
vector<vector<int>> mat(x, vector<int>(y, 100));
if(grid[0][0] == '#')
mat[0][0] = 1;
else
mat[0][0] = 0;
for(int i = 0; i < x; i++){
for(int j = 0; j < y; j++){
if(i + 1 < x){
mat[i + 1][j] = min(mat[i + 1][j], mat[i][j] + (grid[i + 1][j] == '#' && grid[i][j] == '.'));
}
if(j + 1 < y){
mat[i][j + 1] = min(mat[i][j + 1],mat[i][j]+(grid[i][j + 1] == '#' && grid[i][j] == '.'));
}
}
}
return mat[x - 1][y - 1];
}
int main() {
int x = 4, y = 4;
vector<string> grid = {"..#.", "#.#.", "#.##", "###."};
cout<< solve(x, y, grid);
return 0;
} 입력
4, 4, {"..#.", "#.#.", "#.##", "###."} 출력
1