Untitled
plain_text
25 days ago
2.5 kB
3
Indexable
Never
#include <iostream> #define MIN 999999999 using namespace std; int arr[101][101]; int n, m; int dR[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; int dC[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; int len[101][101]; int visited[101][101]; int visited1[101]; int dem; int kc[101][101][101]; int Min; int cost; typedef struct Point { int x, y; }; Point D[101]; typedef struct Queue{ int front, rear; Point data[1000001]; }; void init(Queue &Q){ Q.front = Q.rear = -1; } void push(Queue &Q, Point value){ Q.rear++; Q.data[Q.rear] = value; } Point top(Queue &Q){ Point temp; Q.front++; temp = Q.data[Q.front]; Q.front--; return temp; } void pop(Queue &Q){ Q.front++; } bool empty(Queue &Q){ if(Q.front == Q.rear) return true; return false; } Queue Q; void BFS(Point P){ init(Q); push(Q, P); visited[P.x][P.y] = 1; len[P.x][P.y] = 0; while(!empty(Q)){ Point P1; P1 = top(Q); pop(Q); for(int k=0; k<8; k++){ int x = P1.x + dR[k]; int y = P1.y + dC[k]; if(x>=0 && x<n && y>=0 && y<m && visited[x][y] == 0){ visited[x][y] = 1; len[x][y] = len[P1.x][P1.y] + 1; Point P2; P2.x = x; P2.y = y; push(Q, P2); } } } } void BackTrack(int i, int k){ if(k == dem){ Min = min(Min, cost); return; } if(cost >= Min){ return; } for(int j=1; j<dem; j++){ if(visited1[j] == 0 && i!=j){ visited1[j] = 1; cost += kc[i][D[j].x][D[j].y]; BackTrack(j, k + 1); visited1[j] = 0; cost -= kc[i][D[j].x][D[j].y]; } } } int main(){ freopen("vao.txt", "r", stdin); int t; cin >> t; for(int tc=1; tc<=t; tc++){ cin >> n >> m; int xm = -1, ym = -1; dem = 1; for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ cin >> arr[i][j]; if(arr[i][j] == 3 && xm == -1){ D[0].x = i; D[0].y = j; } if(arr[i][j] == 1){ D[dem].x = i; D[dem].y = j; dem++; } } } for(int k=0; k<dem; k++){ for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ visited[i][j] = 0; len[i][j] = 0; } } Point P; P.x = D[k].x; P.y = D[k].y; BFS(P); for(int l=0; l<dem; l++){ kc[k][D[l].x][D[l].y] = len[D[l].x][D[l].y]; } } Min = MIN; visited1[0] = 1; cost = 0; BackTrack(0, 1); cout << "Case #" << tc << endl; cout << Min << endl; } return 0; }