https://www.acmicpc.net/problem/2178
BFS
문제 N×M크기의 배열로 표현되는 미로가 있다.
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M(2≤N, M≤100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. |
code>>
#include <stdio.h>
#include <queue>
#include <string.h>
int maze[101][101];
int visit[101][101];
int max_x, max_y;
int move_x[] = { 0,0,-1,1 };
int move_y[] = { 1,-1,0,0 };
struct Point
{
int X, Y;
public:
Point(int x, int y)
{
this->X = x;
this->Y = y;
}
};
int main()
{
char input[101];
scanf("%d %d", &max_y, &max_x);
for (int i = 0; i < max_y; i++)
{
scanf("%s", &input);
for (int ii = 0; ii < strlen(input); ii++)
{
maze[i][ii] = input[ii] - '0';
}
}
memset(visit, 0, sizeof(visit));
std::queue<Point> q;
q.push(Point(0, 0));
while (!q.empty())
{
auto p = q.front();
q.pop();
if (p.X == max_x - 1 && p.Y == max_y - 1) break;
for (int i = 0; i < 4; i++)
{
int n_x = move_x[i] + p.X, n_y = move_y[i] + p.Y;
if (n_x >= 0 && n_x < max_x
&& n_y >= 0 && n_y < max_y
&& visit[n_y][n_x] == 0
&& maze[n_y][n_x] == 1)
{
q.push(Point(n_x, n_y));
visit[n_y][n_x] = visit[p.Y][p.X] + 1;
}
}
}
printf("%d\n", visit[max_y - 1][max_x - 1] + 1);
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
| 6064>카잉 달력 (0) | 2018.04.07 |
|---|---|
| 1011>Fly me to the Alpha Centauri (0) | 2018.04.07 |
| 1934, 13241>최소공배수 (0) | 2018.03.24 |
| 1057>토너먼트 (0) | 2018.03.24 |
| 9461>파도반 수열 (2) | 2018.03.17 |
