fork download
copy 
  1. #include <stdio.h>
  2. #include <utility>
  3. #include <queue>
  4.  
  5. int result = -1;                                // 결과값을 저장할 변수입니다.
  6. int row, col;                                   // 미로의 크기를 저장할 변수입니다.
  7. char map[101][101] = {0,};                      // 미로의 형태를 저장할 배열입니다.
  8. int visit[101][101] = {0,};                     // 각 칸을 방문했는지 여부를 저장할 배열입니다.
  9. std::queue<std::pair<int, int>> q;              // BFS 알고리즘에 사용할 큐입니다.
  10.  
  11. void BFS()
  12. {
  13.     q.push(std::make_pair(0, 0));               // 시작점을 큐에 추가합니다.
  14.     visit[0][0] = 1;                            // 시작점을 방문했음을 표시합니다.
  15.  
  16.     while (!q.empty())
  17.     {
  18.         int cur_row = q.front().first;          // 큐에서 현재 위치의 행을 가져옵니다.
  19.         int cur_col = q.front().second;         // 큐에서 현재 위치의 열을 가져옵니다.
  20.         int cur_score = visit[cur_row][cur_col]; // 현재 위치까지의 이동 횟수를 가져옵니다.
  21.  
  22.         // 상 방향으로 이동 가능한 경우를 처리합니다.
  23.         if (cur_row > 0 && 
  24.             map[cur_row-1][cur_col] == '1' && 
  25.             (visit[cur_row-1][cur_col] == 0 || visit[cur_row-1][cur_col] > cur_score + 1))
  26.         {
  27.             q.push(std::make_pair(cur_row-1, cur_col));
  28.             visit[cur_row-1][cur_col] = visit[cur_row][cur_col] + 1;
  29.         }
  30.  
  31.         // 하 방향으로 이동 가능한 경우를 처리합니다.
  32.         if (cur_row < row - 1 &&
  33.             map[cur_row+1][cur_col] == '1' &&
  34.             (visit[cur_row+1][cur_col] == 0 || visit[cur_row+1][cur_col] > cur_score + 1))
  35.         {
  36.             q.push(std::make_pair(cur_row+1, cur_col));
  37.             visit[cur_row+1][cur_col] = visit[cur_row][cur_col] + 1;
  38.         }
  39.  
  40.         // 좌 방향으로 이동 가능한 경우를 처리합니다.
  41.         if (cur_col > 0 &&
  42.             map[cur_row][cur_col-1] == '1' &&
  43.             (visit[cur_row][cur_col-1] == 0 || visit[cur_row][cur_col-1] > cur_score + 1))
  44.         {
  45.             q.push(std::make_pair(cur_row, cur_col-1));
  46.             visit[cur_row][cur_col-1] = visit[cur_row][cur_col] + 1;
  47.         }
  48.  
  49.         // 우 방향으로 이동 가능한 경우를 처리합니다.
  50.         if (cur_col < col - 1 &&
  51.             map[cur_row][cur_col+1] == '1' &&
  52.             (visit[cur_row][cur_col+1] == 0 || visit[cur_row][cur_col+1] > cur_score + 1))
  53.         {
  54.             q.push(std::make_pair(cur_row, cur_col+1));
  55.             visit[cur_row][cur_col+1] = visit[cur_row][cur_col] + 1;
  56.         }
  57.  
  58.         q.pop();                                // 현재 위치를 큐에서 제거합니다.
  59.     }
  60. }
  61.  
  62. int main()
  63. {
  64.     scanf("%d %d", &row, &col);                // 미로의 크기를 입력받습니다.
  65.  
  66.     for (int rowIdx = 0; rowIdx < row; rowIdx++)
  67.     {
  68.         scanf("%s", &map[rowIdx]);             // 미로의 형태를 입력받습니다.
  69.     }
  70.  
  71.     BFS();                                      // BFS 알고리즘을 실행합니다.
  72.  
  73.     printf("%d\n", visit[row-1][col-1]);        // 결과값(최소의 칸 수)을 출력합니다.
  74.  
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4
https://ideone.com/pe1rho
language:
C++ (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!