UVa12826 - Incomplete Chessboard(BFS)

題目大意

給你一個西洋棋盤，給你 A、B、C 座標，請透過上下左右、對角線的方式從 A 走到 B 並繞開 C，最短距離為多少？

題目連結

重點觀念

• 最短路徑快速演算法，與 dijkstra 相同，但使用 queue 來實作

分析

• 使用最短路徑快速演算法實作
• 將 C 點一開始就設定為已經過即可。

參考連結

UVa 12826 by morris821028

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 10
#define INF 0x3f3f3f
#define int long long
using namespace std;
int dist[MAXN][MAXN]; //距離
int visit[MAXN][MAXN]; //是否已經歷過
int ax,ay, bx,by, cx,cy; //a,b,c 的座標
int kase = 1;

int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}; //上下左右、對角線
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

int islegal(int x, int y){ //判斷是否越界
    if(x > 8 || x <= 0 || y > 8 || y <= 0) return 0;
    return 1;
}

int spfa(){
    //memset(g, 0x3f, sizeof(dist)); //using visit
    memset(visit, 0, sizeof(visit));
    memset(dist, 0, sizeof(dist));
    visit[cx][cy] = 1; //C 點設為以使用
    visit[ax][ay] = 1; //起點設為已使用
    deque<pair<int,int> > q;
    q.push_back({ax,ay});

    int x, y;
    while(!q.empty()){ //spfa
        int x = q.front().first;
        int y = q.front().second;
        q.pop_front();

        for(int i = 0; i < 8; i++){
            int tx = x+dx[i], ty = y+dy[i];
            if(!visit[tx][ty] && islegal(tx, ty)){
                dist[tx][ty] = dist[x][y] + 1;
                visit[tx][ty] = 1;
                q.push_back({tx,ty});
            }
        }
        if(visit[bx][by]) return dist[bx][by]; //如果已被經歷過，表示找出最佳解。
    }
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    while(cin >> ax >> ay >> bx >> by >> cx >> cy){
        cout << "Case " << kase++ << ": " << spfa() << "\n";
    }
    return 0;
}