大神的世界

簡單來說就是迷宮問題

此處我將原本的地圖從 0~99 改成 1~100

並用 pass 紀錄到各點的最短步數

個人覺得看程式應該就懂了

#include <iostream>
#include <cstring>

using namespace std;

#define upperBound 101
#define lowerBound 0

bool block[upperBound+1][upperBound+1];
int pass[upperBound][upperBound];
int targetX, targetY;
int minStep;

void walk(int x, int y, int step)
{

    if(y <= lowerBound || y >= upperBound || x <= lowerBound || x >= upperBound || block[y][x])
        return;

    if(step >= pass[y][x])
        return;

    pass[y][x] = step;

    if(y == targetY && x == targetX)
        if(step < minStep)
            minStep = step;

    if(!block[y+1][x]){
        walk(x-1, y+3, step+1);
        walk(x+1, y+3, step+1);
    }
    if(!block[y][x+1]){
        walk(x+3, y+1, step+1);
        walk(x+3, y-1, step+1);
    }
    if(!block[y-1][x]){
        walk(x+1, y-3, step+1);
        walk(x-1, y-3, step+1);
    }
    if(!block[y][x-1]){
        walk(x-3, y-1, step+1);
        walk(x-3, y+1, step+1);
    }

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int block_num;
    int x, y;

    int MAX = 1 << 10;

    while(cin >> block_num){

        memset(block, false, sizeof(block));

        for(int i = 1; i<upperBound; i++)
            for(int j = 1; j<upperBound; j++)
                pass[i][j] = MAX;

        for(int i= 0; i<block_num; i++){
            cin >> x >> y;
            block[y+1][x+1] = true;
        }

        minStep = MAX;
        cin >> x >> y >> targetX >> targetY;
        targetX ++, targetY++;

        walk(x+1, y+1, 0);

        if(minStep == MAX)
            cout << "impossible" << endl;
        else
            cout << minStep << endl;
    }

    return 0;
}