2178>미로탐색

https://www.acmicpc.net/problem/2178

BFS

문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 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;

}