BFS 미로 문제 풀이

2 차원 배열 정의:
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
그것 은 미 로 를 나타 낸다. 그 중 1 은 벽 을 나타 내 고 0 은 걸 을 수 있 는 길 을 표시 하 며 가로로 걷 거나 세로 로 걸 을 수 있 을 뿐 비스듬히 걸 을 수 없다. 프로그램 을 짜 서 왼쪽 상단 에서 오른쪽 하단 까지 의 가장 짧 은 노선 의 길 이 를 출력 해 달라 고 요구한다.
Input
첫 번 째 줄 은 테스트 용례 의 숫자 T 로 입력 합 니 다.
다음은 T 개 5.× 5 의 2 차원 배열 은 각각 하나의 미 로 를 나타 낸다.
Output
왼쪽 상단 에서 오른쪽 하단 까지 의 가장 짧 은 경로 의 길이;통로 가 안 되면 출력 - 1.격식 은 예시 와 같다.
 
Sample Input
2
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
 
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 1
0 0 0 1 0
 
Sample Output
8
-1

#include
#include
#include
using namespace std;

int maze[5][5];
int dir[4][2] = { -1, 0, 1, 0, 0, 1, 0, -1 };
int visited[5][5];
struct point
{
	int x;
	int y;
};
queueq;
point pre[5][5];
int dist[5][5];
int lateset_dir[5][5];
stackout_path;
stackout_dir;
bool FindShortestPath(point begin,point end)
{
	q.push(begin);
	while (!q.empty())
	{
		point curr = q.front();
		q.pop();
		visited[begin.x][begin.y] = 1;
		for (int i = 0; i < 4; i++)
		{
			if (curr.x + dir[i][0] == 4 && curr.y + dir[i][1] == 4)
			{
				pre[4][4] = curr;
				dist[4][4] = dist[curr.x][curr.y] + 1;
				lateset_dir[4][4] = i;
				return true;
			}
			int nx = curr.x + dir[i][0];
			int ny = curr.y + dir[i][1];
			if (nx >= 0 && nx <= 4 && ny >= 0 && ny <= 4 && visited[nx][ny] == 0 && maze[nx][ny] == 0)
			{
				visited[nx][ny] = 1;
				point next;
				next.x = nx;
				next.y = ny;
				q.push(next);
				pre[nx][ny] = curr;
				dist[nx][ny] = dist[curr.x][curr.y] + 1;
				lateset_dir[nx][ny] = i;
			}
		}
	}
	return false;
}

void print_path(point p)
{
	point tmp = pre[p.x][p.y];
	if (tmp.x != p.x || tmp.y != p.y)//    
	{
		out_path.push(p);
		out_dir.push(lateset_dir[p.x][p.y]);
		print_path(tmp);
	}
}

void getPath(point p)
{
	point tmp = pre[p.x][p.y];
	while (1)
	{
		if (tmp.x == p.x && tmp.y == p.y)
		{
			break;
		}
		out_path.push(p);
		out_dir.push(lateset_dir[p.x][p.y]);
		p = tmp;
		tmp = pre[tmp.x][tmp.y];
	}
}
int main()
{
	freopen("sample_input.txt", "r", stdin);
	int test_case;
	cin >> test_case;
	for (int t = 0; t < test_case; t++)
	{
		for (int i = 0; i < 5; i++)
		{
			for (int j = 0; j < 5; j++)
			{
				cin >> maze[i][j];
			}
		}
		memset(visited, 0, sizeof(visited));
		//            maze
		while (!q.empty())
		{
			q.pop();
		}
		point begin, end;
		begin.x = 0; begin.y = 0;
		end.x = 4; end.y = 4;
		bool flag = FindShortestPath(begin, end);
		if (flag)
		{
			cout << "Yes" << endl;
			//print_path(end);
			getPath(end);
			while (!out_path.empty())
			{
				point tmp = out_path.top();
				out_path.pop();
				cout << tmp.x << " " << tmp.y << " " << endl;
			}
			while (!out_dir.empty())
			{
				int tmp = out_dir.top();
				out_dir.pop();
				if (tmp == 0)
					cout << "Up " << endl;
				else if (tmp == 1)
					cout << "Down " << endl;
				else if (tmp == 2)
					cout << "Right " << endl;
				else 
					cout << "Left " << endl;
			}
		}	
		else
		{
			cout << "No" << endl;
		}
	}
	
	
}