ZeroJudge A982: 迷宮問題#1

題目敘述

每筆測資第一行有一個正整數N，接下來要輸入一個N*N的二維字串。字串中的字元只會有兩種，'#' 代表路障不可走，'.' 代表路可走。每筆測資的起點都是 (2, 2)，以0-Base的說法會是 (1, 1)，終點是 (N-1, N-1)，同樣在0-Base來看會是 (N-2, N-2)。要求輸出最少要走幾步才會從起點走到終點，如果永遠無法走到終點則輸出 "No solution!"。

範例輸入 #1

9

#########

#.......#

#.#####.#

#.......#

##.#.####

#..#.#..#

#.##.##.#

#.......#

#########

範例輸出 #1

13

解題思路

本題如果使用DFS會有TLE的情況出現，所以只能使用BFS的方式走，當沒有起點時就代表無法走到終點輸出No solution!。當走到終點時可以直接輸出目前的步數，因為先跑到的就會是最近距離。需要注意的是需要有一個Map來存已經走過的點，不能重複走到同一個點不然會有無限迴圈的情況出現。

解題程式碼如下 (僅供參考)：

#include <iostream>
#include <vector>
#include <map>
using namespace std;

vector<vector<char>>v;
int N, minn = 99999;

pair<int, int> axis (int y, int x)
{
    pair<int, int>tmp;
    tmp.first = y;
    tmp.second = x;
    return tmp;
}

void BFS(vector<pair<int, int>>start, int count, map<pair<int, int>, int>MAP)
{
    if (start.size() == 0)
    {
        cout << "No solution!\n";
        return;
    }
    vector<pair<int, int>>newStart;
    for (int i = 0; i<start.size(); i++)
    {
        int y = start[i].first, x = start[i].second;
        MAP[axis(y, x)]++;
        if (y == N-1 && x == N-1)
        {
            cout << count << "\n";
            return;
        }
        if (y-1 >= 0 && v[y-1][x] == '.' && MAP[axis(y-1, x)] == 0) newStart.push_back(axis(y-1, x));
        if (y+1 <= N && v[y+1][x] == '.' && MAP[axis(y+1, x)] == 0) newStart.push_back(axis(y+1, x));
        if (x-1 >= 0 && v[y][x-1] == '.' && MAP[axis(y, x-1)] == 0) newStart.push_back(axis(y, x-1));
        if (x+1 <= N && v[y][x+1] == '.' && MAP[axis(y, x+1)] == 0) newStart.push_back(axis(y, x+1));
    }
    BFS(newStart, count+1, MAP);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i<N; i++)
    {
        vector<char>tmp;
        for (int j = 0; j<N; j++)
        {
            char a;
            cin >> a;
            tmp.push_back(a);
        }
        v.push_back(tmp);
    }
    N--;
    map<pair<int, int>, int>MAP;
    MAP[axis(1, 1)]++;
    vector<pair<int, int>>tmp;
    tmp.push_back(axis(1, 1));
    BFS(tmp, 1, MAP);
}