Untitled
unknown
plain_text
2 years ago
4.0 kB
4
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 Code: #include<iostream> #define max 10005 using namespace std; int n,m,h; int map[105][105]; int diem_ban[2][105]; int visit[105][105]; // xem diem nao da di qua int di[8]={-2, -1, 1, 2, 2, 1, -1, -2 }; int dj[8]={ 1, 2, 2, 1,-1,-2, -2, -1 }; int queuex[100000]; int queuey[100000]; int front= -1; int rear=-1; int dis[105][105]; // ma tran ke khoang cach giua cac diem ban int d[105][105]; // tinh khoang cach int check[105]; int cnt; int tong,kq; void pushq(int x,int y){ if(rear == max-1) rear =-1; rear++; queuex[rear]=x; queuey[rear]=y; } void pop(){ if(front == max-1) front =-1; front++; } bool IsEmpty(){ return front == rear; } bool checkIn(int i ,int j){ if(i>=0 && i<n && j>= 0 && j<m) return true; return false; } void resetvisit(){ for(int i=0; i<n;i++){ for(int j =0; j< m; j++){ visit[i][j] =0; d[i][j] =0; } } } void resetcheck(){ for(int i=0; i<h;i++){ check[i]=0; } } int bfs(int ibd, int jbd, int iket, int jket){ front = rear =-1; pushq(ibd,jbd); resetvisit(); visit[ibd][jbd] = 1; while(!IsEmpty()){ pop(); int i1 = queuex[front]; int j1 = queuey[front]; for(int k=0; k<8;k++){ int i2 = i1 + di[k]; int j2 = j1 + dj[k]; if(checkIn(i2,j2)==true && visit[i2][j2]==0){ // visit[i2][j2] = visit[i1][j1]+1; d[i2][j2] = d[i1][j1]+1; visit[i2][j2] =1; if(i2 == iket && j2 == jket) return d[i2][j2]; pushq(i2,j2); } } } return -1; } void backtrack(int i){ if(cnt ==h-1) { if(kq>tong) kq = tong; return; } int nho = max; for(int j =1; j< h; j++){ if(check[j] ==0 && kq>tong ){ check[j] =1; nho =dis[i][j]; cnt++; tong += nho; backtrack(j); check[j] =0; tong -= nho; cnt--; } } } int main(){ //freopen("Text.txt", "r", stdin); int test; cin >> test; for(int tc =1; tc<=test; tc++){ cin >> n >>m; h=1; for(int i=0; i<n;i++){ for(int j =0; j< m; j++){ cin >> map[i][j]; if(map[i][j] == 3){ diem_ban[0][0]=i; diem_ban[1][0]=j; } else if(map[i][j] == 1){ diem_ban[0][h]=i; diem_ban[1][h]=j; h++; } } } cout << "Case #" << tc << endl; //bfs de tim khoang cach den cac diem ban for(int i=0; i<h;i++){ for(int j =i+1; j< h; j++){ dis[i][j] = bfs(diem_ban[0][i], diem_ban[1][i], diem_ban[0][j], diem_ban[1][j]); dis[j][i] = dis[i][j]; } } cnt =0; tong =0; kq = max; resetcheck(); check[0] =1; backtrack(0); cout << kq << endl; } return 0; }
Editor is loading...