迷宮ナビゲーション(金俊)
2818 ワード
典型的な迷路問題
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int MAX = 100;
int N, M;
int Chk[MAX][MAX] = { 0, };
int Arr[MAX][MAX];
int iResult[MAX][MAX];
int DirX[4] = { -1, 0, 1, 0 };
int DirY[4] = { 0, -1, 0, 1 };
queue<pair<int, int>> qTemp;
int iCount = 1;//맨처음 계산하는 부분은 1을 채워준다.
int iStartX = 0;
int iStartY = 0;
//vector<vector<int>> vTemp = { {1,0,1,1,1,1},{1,0,1,0,1,0},{1,0,1,0,1,1},{1,1,1,0,1,1} };
void BFS(int x, int y)
{
Chk[x][y] = 1;
iResult[x][y] = 1;
qTemp.push(make_pair(x, y));
while (!qTemp.empty())
{
x = qTemp.front().first;
y = qTemp.front().second;
qTemp.pop();
for (int i = 0; i < 4; i++)
{
int nx = x + DirX[i];
int ny = y + DirY[i];
if ((Chk[nx][ny] == 0 ) && (nx >= 0) && (nx < N) && (ny >= 0) && (ny < M) && (Arr[nx][ny] == 1))//1. 방문 안했고, 2. X바운더리, Y바운더리 안넘고,
{
Chk[nx][ny]= 1;
qTemp.push(make_pair(nx, ny));
iResult[nx][ny] = iResult[x][y]+1;
}
}
}
}
int main()
{
cin >> N ;//이부분 Y
cin >> M ;//이부분 X
scanf("%d %d", &N, &M);
/* 그래프 정보 입력 */
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
scanf("%1d", &Arr[i][j]);
}
}
//for (int i = 0; i < N; i++)
//{
// for (int j = 0; j < M; j++)
// {
// cin >> Arr[i][j];
// }
//}
BFS(0, 0);
int OutData = iResult[N - 1][M - 1];
cout << OutData;
return 0;
}
この問題は白準の答えではできないがTestCaseはよく出ている.1.指向性x,y Array
2.アクセスチェックとアクセス長の決定Chk,Arr 2 D
3.初回プッシュ、while(!qTemp.empt()->上下左右ナビゲーション->およびセーフティバーとのアクセスレコード(0)、長さは同じでなければならない(1)
[原句]この時点で開始します.キューにプッシュし、アクセス履歴=1をチェックし、結果値=前の結果値+1(結果[nx][ny]=result[x][y]+1)
この構造に詳しい
Reference
この問題について(迷宮ナビゲーション(金俊)), 我々は、より多くの情報をここで見つけました https://velog.io/@imalive77/미로-탐색백준テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol