【ACM- OJ】《迷宮問題》C++

• 題目描述
• 輸入
• 輸出
• 樣例輸入
• 樣例輸出
• AC代碼

題目描述

定義一個二維數組：

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,
           

};

它表示一個迷宮，其中的1表示牆壁，0表示可以走的路，隻能橫着走或豎着走，不能斜着走，要求程式設計式找出從左上角到右下角的最短路線。

輸入

一個5 × 5的二維數組，表示一個迷宮。資料保證有唯一解。

輸出

左上角到右下角的最短路徑，格式如樣例所示。

樣例輸入

0 1 0 0 0

0 1 0 1 0

0 0 0 0 0

0 1 1 1 0

0 0 0 1 0

樣例輸出

(0, 0)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)

AC代碼

//
//  main.cpp
//  迷宮問題
//
//  Created by HISS on 2020/10/24.
//  Copyright © 2020 HISS. All rights reserved.
//

#include<iostream>
#include<stack>
using namespace std;

int i, j, ff, num, front, a[5][5], b[5][5], c[5][5];
stack<int>x;
stack<int>y;

void dfs(int i,int j)
{
    if(a[i][j] == 1 || i < 0 || j < 0 || i >= 5 || j >= 5 || b[i][j] == 1)
        return ;
    if(c[i][j] == 0 && a[i][j] == 0 && b[i][j] == 0)
    {
        c[i][j] = ff;   //路線的第幾個節點
        b[i][j] = 1;    //通路過
        ff ++;
    }
    dfs(i, j + 1);
    dfs(i + 1, j);
    dfs(i - 1, j);
    dfs(i, j - 1);
}

int main()
{
    //輸入迷宮
    for(i = 0; i < 5; i ++)
        for(j = 0; j < 5; j ++)
        {
            cin >> a[i][j];
            b[i][j] = 0;
            c[i][j] = 0;
        }
    ff = 1;
    //每個點都深搜一次
    for(i = 0; i < 5; i ++)
    {
        for(j = 0; j < 5; j ++)
        {
            if(a[i][j] == 0)
                dfs(i, j);
        }
    }
    //從最後一個節點倒着尋找
    front = c[4][4];
    int fu = front;
    for(num = fu - 1; num > 0; num --)
    {
        for(i = 4; i >= 0; i --)
        {
            for(j = 4; j >= 0; j --)
            {
                if(c[i][j] == front - 1 && c[i][j] != 0)
                {
                    //倒序路線c[i][j]
                    x.push(i);
                    y.push(j);
                    front = c[i][j];
                }
            }
        }
    }
    //輸出路線，按出棧順序
    while(!x.empty() && !y.empty())
    {
        cout << "(" << x.top() << ", " << y.top() << ")" << endl;
        x.pop();
        y.pop();
    }
    cout << "(" << 4 << ", "<< 4 << ")" << endl;
    return 0;
}