Quân tượng
Xét bàn cờ vuông kích thước n×n. Các dòng được đánh số từ 1 đến n, từ dưới lên trên. Các cột được đánh số từ 1 đến n từ trái qua phải.
Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên bàn cờ có m (0 ≤ m ≤ n) quân cờ. Với m > 0, quân cờ thứ i ở ô (ri, ci), i = 1,2,…, m. Không có hai quân cờ nào ở trên cùng một ô. Trong số các ô còn lại của bàn cờ, tại ô (p, q) có một quân tượng. Mỗi một nước đi, từ vị trí đang đứng quân tượng chỉ có thể di chuyển đến được những ô trên cùng đường chéo với nó mà trên đường đi không phải qua các ô đã có quân
Cần phải đưa quân tượng từ ô xuất phát (p, q) về ô đích (s,t).
Cho kích thước bàn cờ n, số quân cờ hiện có trên bàn cờ m và vị trí của chúng, ô xuất phát và ô đích của quân tượng. Hãy xác định số nước đi ít nhất cần thực hiện để đưa quân tượng về ô đích hoặc đưa ra số -1 nếu điều này không thể thực hiện được.
Constraints
N = 1~200
Input
Dòng đầu tiên chứa số testcase. Mỗi testcase có cấu trúc như sau:
Dòng thứ nhất chứa 6 số nguyên n, m, p, q, s, t.
Nếu m > 0 thì mỗi dòng thứ i trong m dòng tiếp theo chứa một cặp số nguyên ri , ci xác định vị trí quân thứ i.
Hai số liên tiếp trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Output
Với mỗi test case in ra 1 dòng duy nhất là số nước đi tìm được.
Sample
Input
2
5 5 5 5 5 3
1 2
1 5
2 2
4 2
4 3
8 3 7 2 1 4
5 4
3 4
4 7
Output
2
3
Code Java:
package practice;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
/*
* link đề bài: https://alexishuuuocn.wordpress.com/2019/07/07/quan-tuong/
* quân tượng trong cờ vua đi theo 4 phía đường chéo có thể hết bản đồ luôn
* khác với quân tượng trong cờ tướng đi theo kiểu chèo 2×2
*/
public class QuanTuong {
static int n, m, p, q, s, t, testCase, x, y, st, en;
static int[][] map;
static int[][] visit;
static int[] dx = { 1, 1, -1, -1 };
static int[] dy = { 1, -1, 1, -1 };
static int[] queueX = new int[1000000];
static int[] queueY = new int[1000000];
static void BFS(int startX, int startY) {
st = en = 0;
queueX[en] = startX;
queueY[en] = startY;
en++;
visit[startX][startY] = 1;
while (st != en) {
int x = queueX[st];
int y = queueY[st];
st++;
for (int i = 0; i < 4; i++) {
for (int k = 1; k <= n; k++) {
int xNext = x + dx[i] * k;
int yNext = y + dy[i] * k;
if (xNext >= 1 && xNext <= n && yNext >= 1 && yNext <= n) {
if (visit[xNext][yNext] == 0 && map[xNext][yNext] != 1) {
queueX[en] = xNext;
queueY[en] = yNext;
en++;
visit[xNext][yNext] = visit[x][y] + 1;
}
// nếu vị trí đó có quân đang đứng rồi thì ko được đi vào && dừng lại chuyển hướng khác
else if(visit[xNext][yNext] == -1) {
break;
}
}
}
}
}
}
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream(“QuanTuong.txt”));
Scanner sc = new Scanner(System.in);
testCase = sc.nextInt();
for (int tc = 1; tc <= testCase; tc++) {
n = sc.nextInt();
m = sc.nextInt();
p = sc.nextInt();
q = sc.nextInt();
s = sc.nextInt();
t = sc.nextInt();
map = new int[n + 1][n + 1];
visit = new int[n + 1][n + 1];
map[p][q] = 10000;
map[s][t] = 10000;
// đánh dấu vị trí có quân đang đứng
for (int i = 0; i < m; i++) {
x = sc.nextInt();
y = sc.nextInt();
map[x][y] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (map[i][j] == 1) {
visit[i][j] = -1;
}
}
}
BFS(p, q);
System.out.println(“Case #” + tc + ” ” + (visit[s][t] – 1));
}
}
}
alexishuuuocn 