2178번: 미로 탐색

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

구현 아이디어 0분 구현 20분

풀이

• 각각의 수들은 붙어서 입력으로 주어진다.

2 25
1011101110111011101110111
1110111011101110111011101	//  2 ≤ input.length() ≤ 100

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
int N, M;
vector<vector<int>> Maps(101, vector<int>(101, 0));
int DirRow[4]{-1, 0, 1, 0};
int DirCol[4]{0, 1, 0, -1};

struct Position
{
    int Row, Col, Sum;
    Position(int Row, int Col, int Sum)
    {
        this->Row = Row;
        this->Col = Col;
        this->Sum = Sum;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("input.txt", "rt", stdin);

    cin >> N >> M;

    for (int i = 1; i <= N; ++i)
    {
        string StrBoard;
        cin >> StrBoard;
        for (int j = 1; j <= M; ++j)
        {
            Maps[i][j] = (StrBoard[j - 1] - '0');
        }
    }

    queue<Position> Q;
    Q.push(Position(1, 1, 1));
    Maps[1][1] = 0;

    while (!Q.empty())
    {
        Position CurrentPosition = Q.front();
        Q.pop();

        if (CurrentPosition.Row == N &&
            CurrentPosition.Col == M)
        {
            cout << CurrentPosition.Sum;
            break;
        }

        for (int i = 0; i < 4; ++i)
        {
            int NextRowPosition = CurrentPosition.Row + DirRow[i];
            int NextColPosition = CurrentPosition.Col + DirCol[i];

            if (NextRowPosition < 1 || NextColPosition < 1 ||
                NextRowPosition > N || NextColPosition > M ||
                !Maps[NextRowPosition][NextColPosition]) continue;

            Q.push(Position(NextRowPosition, NextColPosition, CurrentPosition.Sum + 1));
            Maps[NextRowPosition][NextColPosition] = 0;
        }
    }

    return 0;
}