【題目敘述】https://zerojudge.tw/ShowProblem?problemid=b059
【解題想法】BFS
- g[x][y]:紀錄座標點 (x, y) 位置的狀態
- -1:有障礙物
- 0:尚未拜訪過 (為了不與此狀態衝突,起點的使用步數設為 1,因此最後答案要減 1。)
- > 0:行經此點使用的步數
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ms(i) memset(i, 0, sizeof(i))
#define pii pair<int,int>
#define F first
#define S second
int g[105][105];
int dx[] = {-3, -3, -1, 1, 3, 3, 1, -1};
int dy[] = {1, -1, -3, -3, -1, 1, 3, 3};
int check[][2] = {{-1, 0}, {-1, 0}, {0, -1}, {0, -1}, {1, 0}, {1, 0}, {0, 1}, {0, 1}};
pii dst, now;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, x, y, nx, ny;
while (cin >> n){
ms(g);
for (int i=0; i<n; i++){
cin >> x >> y;
g[x][y] = -1;
}
cin >> x >> y;
queue <pii> q;
q.push({x, y});
g[x][y] = 1;
cin >> dst.F >> dst.S;
bool canFind = false;
while (!q.empty()){
now = q.front();
q.pop();
x = now.F;
y = now.S;
for (int i=0; i<8; i++){
nx = x + check[i][0];
ny = y + check[i][1];
if (nx < 0 || nx > 99 || ny < 0 || ny > 99 || g[nx][ny] == -1) continue;
nx = x + dx[i];
ny = y + dy[i];
if (nx < 0 || nx > 99 || ny < 0 || ny > 99 || g[nx][ny] != 0) continue;
q.push({nx, ny});
g[nx][ny] = g[x][y] + 1;
if (nx == dst.F && ny == dst.S){
canFind = true;
break;
}
}
}
if (canFind) cout << g[dst.F][dst.S] - 1 << '\n';
else cout << "impossible\n";
}
}
Python code (credit: Amy Chou)
import sys
for line in sys.stdin:
n = int(line)
g = [[0 for j in range(100)] for i in range(100)]
dx = [-3, -3, -1, 1, 3, 3, 1, -1]
dy = [1, -1, -3, -3, -1, 1, 3, 3]
check = [(-1, 0), (-1, 0), (0, -1), (0, -1), (1, 0), (1, 0), (0, 1), (0, 1)]
for _ in range(n):
x, y = map(int, sys.stdin.readline().split())
g[x][y] = -1
x, y = map(int, sys.stdin.readline().split())
q = [(x, y)]
g[x][y] = 1
dst_x, dst_y = map(int, sys.stdin.readline().split())
canFind = False
while q:
x, y = q.pop(0)
for i in range(8):
nx = x + check[i][0]
ny = y + check[i][1]
if nx < 0 or nx > 99 or ny < 0 or ny > 99 or g[nx][ny] == -1:
continue
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx > 99 or ny < 0 or ny > 99 or g[nx][ny] != 0:
continue
q.append((nx, ny))
g[nx][ny] = g[x][y] + 1
if nx == dst_x and ny == dst_y:
canFind = True
break
if canFind:
print(g[dst_x][dst_y] - 1)
else:
print("impossible")