迷宮ナビゲーション(金俊)



典型的な迷路問題
#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)
この構造に詳しい