2x3 보드 하나가 있고 1에서 5까지의 숫자로 표시되는 5개의 타일이 있고 0으로 표시되는 빈 사각형 하나가 있다고 가정합니다.
여기에서 이동은 0과 하나의 인접한 숫자(상단, 하단, 왼쪽 또는 오른쪽)를 의미하며 교체합니다. 이것은 요소가 [[1,2,3],[4,5,0]]과 같은 방식으로 배열될 때 해결됩니다.
퍼즐 보드가 있습니다. 우리는 보드의 상태를 해결하기 위해 필요한 최소 이동 수를 찾아야 합니다. 해결할 수 없으면 -1을 반환합니다.
따라서 입력이 [[1,2,3],[0,4,5]]와 같으면 [0,4]와 [0,5]를 바꿔야 하므로 출력은 2가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
하나의 함수slidingPuzzle()을 정의하면 보드가 입력으로 사용됩니다.
-
보드가 완벽하게 배열된 경우 -
-
0 반환
-
-
2d 행렬의 하나의 대기열 q 정의
-
q에 보드 삽입
-
2D 행렬에 대해 방문한 세트 하나 정의
-
방문한 페이지에 보드 삽입
-
initialize lvl :=1의 경우 q가 비어 있지 않으면 업데이트(lvl을 1씩 증가)하고 -
를 수행합니다.-
sz :=q의 크기
-
sz가 0이 아닌 동안 각 반복 후에 sz를 감소시키고 -
-
하나의 2D 배열 노드 정의 =q의 앞 요소
-
q에서 요소 삭제
-
dx :=-1, y :=-1
-
for initialize i :=0, i <보드 크기일 때 업데이트(i 1 증가), −
-
j 초기화의 경우 :=0, j <보드[0]의 크기일 때 업데이트(j를 1만큼 증가), 수행 -
-
노드[i, j]가 0과 같으면 -
-
x :=나는
-
y :=j
-
루프에서 나오세요
-
-
-
-
초기화 k :=0의 경우 k <4일 때 업데이트(k를 1만큼 증가), −
-
nx <0 또는 ny <0 또는 nx>=보드의 행 개수 또는 ny>=보드의 열 개수인 경우 -
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
교환 노드[x, y] 및 노드[nx, ny]
-
노드가 방문 중인 경우 -
-
교환 노드[x, y] 및 노드[nx, ny]
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
방문한 노드에 삽입
-
노드가 보드의 완벽한 배열인 경우 -
-
레벨 반환
-
-
q에 노드 삽입
-
교환 노드[x, y] 및 노드[nx, ny]
-
-
-
반환 -1
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
bool ok(vector < vector <int> >& b){
return b[0][0] == 1 && b[0][1] == 2 && b[0][2] == 3 && b[1]
[0] == 4 && b[1][1] == 5;
}
int slidingPuzzle(vector<vector<int>>& board) {
if (ok(board))
return 0;
queue<vector<vector<int> > > q;
q.push(board);
set<vector<vector<int> > > visited;
visited.insert(board);
for (int lvl = 1; !q.empty(); lvl++) {
int sz = q.size();
while (sz--) {
vector<vector<int> > node = q.front();
q.pop();
int x = -1;
int y = -1;
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++) {
if (node[i][j] == 0) {
x = i;
y = j;
break;
}
}
}
for (int k = 0; k < 4; k++) {
int nx = x + dir[k][0];
int ny = y + dir[k][1];
if (nx < 0 || ny < 0 || nx >= board.size() || ny
>= board[0].size())
continue;
swap(node[x][y], node[nx][ny]);
if (visited.count(node)) {
swap(node[x][y], node[nx][ny]);
continue;
}
visited.insert(node);
if (ok(node))
return lvl;
q.push(node);
swap(node[x][y], node[nx][ny]);
}
}
}
return -1;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,2,3},{0,4,5}};
cout << (ob.slidingPuzzle(v));
} 입력
{{1,2,3},{0,4,5}} 출력
2