Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 미로의 모서리 셀에서 중간 셀까지의 경로 찾기

<시간/>

숫자로 채워진 정사각형 미로가 있다고 가정합니다. 모서리 셀에서 중간 셀까지의 모든 경로를 찾아야 합니다. 여기에서 우리는 셀에서 위, 아래, 오른쪽, 왼쪽의 4방향으로 정확히 n 단계를 진행할 것입니다. 여기서 n은 셀의 값입니다. 따라서 셀 [i,j]에서 셀 [i+n,j]에서 [i-n, j], [i, j+n] 및 [i, j-n]으로 이동할 수 있습니다. 여기서 n은 셀 [ 나, 지].

따라서 입력이 다음과 같으면

3 4 4 4 7 3 4 6 3
6 7 5 6 6 2 6 6 2
3 3 4 3 2 5 4 7 2
6 5 5 1 2 3 6 5 6
3 3 4 3 0 1 4 3 4
3 3 4 3 2 1 3 3 5
3 5 4 3 2 6 4 4 3
3 5 1 3 7 5 3 6 3
6 2 4 3 4 5 4 5 1

그러면 출력은

  • (0, 0)→(0, 3)→(0, 7)→(6, 7)→(6, 3)→(3, 3)→(3, 4)→(5, 4)→(5 , 2)→(1, 2)→(1, 7)→(7, 7)→(7, 1)→(2, 1)→(5, 1)→(0, 1)→(4, 1 )→(4, 4)→중간

  • (0, 0)→(0, 3)→(0, 7)→(6, 7)→(6, 3)→(3, 3)→(3, 4)→(5, 4)→(5 , 2)→(1, 2)→(1, 7)→(7, 7)→(7, 1)→(2, 1)→(2, 4)→(4, 4→중간

  • (0, 0)→(0, 3)→(0, 7)→(0, 1)→(4, 1)→(7, 1)→(2, 1)→(2, 4)→(4 , 4)→중간

  • (0, 0)→(0, 3)→(0, 7)→(0, 1)→(4, 1)→(4, 4)→중간

  • (8, 8)→(7, 8)→(4, 8)→(4, 4)→중간

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • N :=9

  • is_ok() 함수를 정의합니다. 이것은 방문이라고 하는 한 쌍의 세트, 한 쌍의 pt,

  • 범위 0에서 N에 있는 pt의 첫 번째 및 두 번째 요소와 pt가 방문하지 않은 경우 true를 반환합니다.

  • 배열 dir_row 정의 :={ - 1, 1, 0, 0}

  • 배열 dir_col 정의 :={ 0, 0, - 1, 1}

  • 배열 행 정의 :={ 0, 0, N - 1, N - 1}

  • 배열 정의 col :={ 0, N - 1, 0, N - 1}

  • solve() 함수를 정의하면 미로, 경로, 방문한 쌍 한 세트, Curr 한 쌍이 필요합니다.

  • curr의 첫 번째와 두 번째가 N / 2와 같으면 -

    • 경로 표시

    • 반환

  • initialize i :=0의 경우, i <4일 때 업데이트(i를 1만큼 증가), 수행 -

    • n :=미로[curr.first, curr.second]

    • x :=curr.first + dir_row[i] * n

    • y :=curr.second + dir_col[i] * n

    • n :=x, y를 사용하는 쌍

    • is_ok(방문, 다음)인 경우 -

      • 방문에 다음 삽입

      • 경로 끝에 다음 삽입

      • 해결(미로, 경로, 방문, 다음)

      • 경로에서 마지막 요소 삭제

      • 방문에서 다음 삭제

  • 기본 방법에서 다음을 수행하십시오 -

  • 방문이라고 하는 한 쌍의 집합을 정의합니다.

  • initialize i :=0의 경우, i <4일 때 업데이트(i를 1만큼 증가), 수행 -

    • x :=행[i]

    • y :=열[i]

    • pt :=(x, y)를 사용하여 쌍 만들기

    • 방문한 페이지에 pt 삽입

    • 경로 끝에 pt 삽입

    • 해결(미로, 경로, 방문, pt)

    • 경로에서 마지막 요소 삭제

    • 방문한 페이지에서 pt ​​삭제

예시(C++)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
#define N 9
bool is_ok(set<pair<int, int> > visited, pair<int, int> pt) {
   return (pt.first >= 0) && (pt.first < N) && (pt.second >= 0) && (pt.second < N) && (visited.find(pt) == visited.end());
}
void display_path(list<pair<int, int> > path) {
   for (auto it = path.begin(); it != path.end(); it++)
   cout << "(" << it->first << ", " << it->second << ")->";
   cout << "MIDDLE" << endl << endl;
}
int dir_row[] = {-1, 1, 0, 0};
int dir_col[] = { 0, 0, -1, 1};
int row[] = { 0, 0, N-1, N-1};
int col[] = { 0, N-1, 0, N-1};
void solve(int maze[N][N], list<pair<int, int> > &path, set<pair<int, int> > &visited, pair<int, int> &curr) {
   if (curr.first == N / 2 && curr.second == N / 2) {
      display_path(path);
      return;
   }
   for (int i = 0; i < 4; ++i) {
      int n = maze[curr.first][curr.second];
      int x = curr.first + dir_row[i]*n;
      int y = curr.second + dir_col[i]*n;
      pair<int, int> next = make_pair(x, y);
      if (is_ok(visited, next)) {
         visited.insert(next);
         path.push_back(next);
         solve(maze, path, visited, next);
         path.pop_back();
         visited.erase(next);
      }
   }
}
void search_path(int maze[N][N]) {
   list<pair<int, int> > path;
   set<pair<int, int> > visited;
   for (int i = 0; i < 4; ++i) {
      int x = row[i];
      int y = col[i];
      pair<int, int> pt = make_pair(x, y);
      visited.insert(pt);
      path.push_back(pt);
      solve(maze, path, visited, pt);
      path.pop_back();
      visited.erase(pt);
   }
}
int main() {
   int maze[N][N] = {
      {3, 4, 4, 4, 7, 3, 4, 6, 3},
      {6, 7, 5, 6, 6, 2, 6, 6, 2},
      {3, 3, 4, 3, 2, 5, 4, 7, 2},
      {6, 5, 5, 1, 2, 3, 6, 5, 6},
      {3, 3, 4, 3, 0, 1, 4, 3, 4},
      {3, 5, 4, 3, 2, 1, 3, 3, 5},
      {3, 5, 4, 3, 2, 6, 4, 4, 3},
      {3, 5, 1, 3, 7, 5, 3, 6, 3},
      {6, 2, 4, 3, 4, 5, 4, 5, 1}
   };
   search_path(maze);
}

입력

{{3, 4, 4, 4, 7, 3, 4, 6, 3},
{6, 7, 5, 6, 6, 2, 6, 6, 2},
{3, 3, 4, 3, 2, 5, 4, 7, 2},
{6, 5, 5, 1, 2, 3, 6, 5, 6},
{3, 3, 4, 3, 0, 1, 4, 3, 4},
{3, 5, 4, 3, 2, 1, 3, 3, 5},
{3, 5, 4, 3, 2, 6, 4, 4, 3},
{3, 5, 1, 3, 7, 5, 3, 6, 3},
{6, 2, 4, 3, 4, 5, 4, 5, 1}}

출력

(0, 0)->(0, 3)->(0, 7)->(6, 7)->(6, 3)->(3, 3)->(3, 4)->(5, 4)->(5, 2)->(1, 2)->(1, 7)->(7, 7)->(7, 1)->(2, 1)->(5, 1)->(0, 1)->(4, 1)->(4, 4)->MIDDLE
(0, 0)->(0, 3)->(0, 7)->(6, 7)->(6, 3)->(3, 3)->(3, 4)->(5, 4)->(5, 2)->(1, 2)->(1, 7)->(7, 7)->(7, 1)->(2, 1)->(2, 4)->(4, 4)->MIDDLE
(0, 0)->(0, 3)->(0, 7)->(0, 1)->(4, 1)->(7, 1)->(2, 1)->(2, 4)->(4, 4)->MIDDLE
(0, 0)->(0, 3)->(0, 7)->(0, 1)->(4, 1)->(4, 4)->MIDDLE
(8, 8)->(7, 8)->(4, 8)->(4, 4)->MIDDLE