ZeroJudge A982: 迷宮問題#1

給你一個 N＊N 格的迷宮，迷宮中以「#」代表障礙物，以「.」代表路。

你固定在 (2, 2) 出發，最左上角是 (1, 1)，目的地是 (N-1, N-1)。

求包括起點和終點，最少路徑的長度。

範例測資

範例輸入範例輸出
第一行有一個正整數 N (N 不超過 100)
接下來有 N 行 N 列，由「#」和「.」組成的迷宮		一個正整數，代表最短路徑的長度
如果不可能到達終點，則印出「No solution!」
9
(迷宮請見下表格)		13

輸入迷宮表格

#########
#.......#
#.#####.#
#.......#
##.#.####
#..#.#..#
#.##.##.#
#.......#
#########
ZeroJudge A982 輸入測資表格

解題思路

本題如果使用DFS會有TLE的情況出現，所以只能使用BFS的方式走，當沒有起點時就代表無法走到終點輸出No solution!。

當走到終點時可以直接輸出目前的步數，因為先跑到的就會是最短距離。

需要注意的是需要有一個 Map 來存已經走過的點，不能重複走到同一個點不然會有無限迴圈的情況出現。

範例程式碼－ZeroJudge A982: 迷宮問題#1

#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);
}

//ZeroJudge A982
//Dr. SeanXD
標籤

相關文章

發佈留言