Untitled
unknown
plain_text
2 years ago
7.8 kB
6
Indexable
Quân mã
Trong một bàn cờ NxM.
Tìm số lần đi tối thiểu để quân mã ăn hết quân địch.
Quân mã có thể di chuyển xung quanh theo 8 hướng .(H1)
H1
Example : test case 1
Quân mã mất 3 lần di chuyển để ăn hết quân địch . (2,3) -> (3,5) -> (4,3)
H2
Input : dòng đầu tiên là số lương test case
Dòng 2 là kích thước của bàn cờ
Tiếp theo là bàn cờ :
3 là vị trí xuất phát của quân mã
1 là vị trí quân địch
0 là vị trí trống.
Quân mã có thể di chuyển trên tất cả các vị trí trên bàn cờ (0,1,3).
Output:
In ra số lần di chuyển nhỏ nhất để quân mã ăn hết quân địch.
Sample input:
2
5 7
0 0 0 0 0 0 0
0 3 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 1 0
0 0 0 1 0 0 0
10 10
1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 3 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1
Sample output:
Case #1
3
Case #2
12
//////////////////////////////////////////////////
#include<iostream>
#define oo 100000
#define max 100
using namespace std;
int n, m, front, rear, dem;
int Map[max][max], visit[max][max];
int qx[oo], qy[oo];
int com[max][2], dis[max][max];
int vs[max];
int dx[8] = {-2,-1, 1, 2, 2, 1,-1,-2};
int dy[8] = { 1, 2, 2, 1,-1,-2,-2,-1};
int ans;
void push(int x, int y){
if(front == -1) front = 0;
rear++;
qx[rear] = x;
qy[rear] = y;
}
void pop(){
if(front >= rear) front = rear = -1;
else front++;
}
bool isEmpty(){
return front == -1;
}
void reset_bfs(){
front = rear = -1;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
visit[i][j] = 0;
}
}
}
void bfs(int x, int y, int u){
reset_bfs();
visit[x][y] = 0;
push(x,y);
while(!isEmpty()){
int topx = qx[front];
int topy = qy[front];
pop();
for(int i = 0; i < 8; i++){
int tempx = topx + dx[i];
int tempy = topy + dy[i];
if( tempx >= 0 && tempx < n && tempy >= 0 && tempy < m && visit[tempx][tempy] == 0){
visit[tempx][tempy] = visit[topx][topy] + 1;
push(tempx,tempy);
if(Map[tempx][tempy] == 1 || Map[tempx][tempy] == 3){
for(int j = 0; j < dem; j++){
if(tempx == com[j][0] && tempy == com[j][1]){
dis[u][j] = visit[tempx][tempy];
}
}
}
}
}
}
}
void backtrack(int x, int sum, int y){
if(y == dem){
if(ans > sum) {
ans = sum;
return;
}
}
if(sum > ans) return;
for(int i = 0; i < dem ; i++){
if(vs[i] == 0 && dis[x][i] > 0){
vs[i] = 1;
backtrack(i,sum+dis[x][i],y+1);
vs[i] = 0;
}
}
}
void reset(){
dem = 1;
ans = oo;
// reset mang kooang cach tu cac vi tri
for(int i = 0; i < max; i++){
vs[i] = 0;
com[i][0] = com[i][1] = 0;
for(int j = 0; j < max; j++){
dis[i][j] = 0;
Map[i][j] = -1;
}
}
}
int main(){
// freopen("input.txt","r", stdin);
int tc;
cin >> tc;
for(int T = 1; T <= tc; T++){
cin >> n >> m;
reset();
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> Map[i][j];
// 3 vi tri xuat phai cua quan ma
// 1 la vi tri quan dich
// 0 vi tri trong
if(Map[i][j] == 3){
com[0][0] = i;
com[0][1] = j;
}
if(Map[i][j] == 1){
com[dem][0] = i;
com[dem][1] = j;
dem++;
}
}
}
for(int i = 0; i < dem; i++){
bfs(com[i][0], com[i][1], i);
}
vs[0] = 1;
backtrack(0,0,1);
cout << "Case #" << T << endl;
cout << ans << endl;
}
return 0;
}
///////////////////////////////////////////////////
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
///////////////////////////////////
#include<iostream>
#define oo 100000
#define max 205
using namespace std;
int ans;
int N, M, p, q, s, t;
int visit[max][max];
int qx[oo];
int qy[oo];
int front, rear;
int dx[] = {-1, 1, 1,-1};
int dy[] = {-1, 1,-1, 1};
int visitBfs[max][max];
bool isEmpty(){
return front == -1;
}
void push(int x, int y){
if (front == -1) front = 0;
rear++;
qx[rear] = x;
qy[rear] = y;
}
void pop(){
if (front >= rear) front = rear = -1;
else front++;
}
int bfs(int x, int y){
front = rear = -1;
push(x,y);
visitBfs[x][y] = 0;
while (!isEmpty()){
int x1 = qx[front];
int y1 = qy[front];
pop();
for (int i = 0; i < 4; i++){
for (int k = 1; k <= 200; k++){
int x2 = x1 + k*dx[i];
int y2 = y1 + k*dy[i];
if (x2>=1 && x2<=N && y2>=1 && y2<=N){
// nhay vao vi tri cua co chot thi loai
if (visit[x2][y2] == 1) break;
// nhay
if (visitBfs[x2][y2]==0 && visit[x2][y2] != 1){
push(x2,y2);
visitBfs[x2][y2] = visitBfs[x1][y1]+1;
if (visit[x2][y2] == 2){
return visitBfs[x2][y2];
}
}
}
}
}
}
return -1;
}
void reset(){
ans = 0;
for (int i = 1; i <= N; i++){
for (int j = 1; j <= N; j++){
visit[i][j] = 0;
visitBfs[i][j] = 0;
}
}
}
int main(){
// freopen("input.txt", "r", stdin);
int TC; cin >> TC;
for (int tc = 1; tc <= TC; tc++){
cin >> N >> M >> p >> q >> s >> t;
//ô xuất phát (p, q) về ô đích (s,t)
reset();
// xu ly vi trong mang dang cho la N la 1 va 1 den N
p = N+1-p;
s = N+1-s;
// 2 la dich den
// 1 la cac quan dat tren ban co khong bij vi pham vao
visit[s][t] = 2;
for (int i = 1; i <= M; i++){
int r, c;
cin >> r >> c;
visit[N+1-r][c] = 1;
}
ans = bfs(p,q);
cout << ans << endl;
}
return 0;
}Editor is loading...