Untitled
unknown
plain_text
24 days ago
3.3 kB
2
Indexable
Never
#include <iostream> using namespace std; int T, N, M; int arr[105][105]; int visited[105][105]; int posX[10001]; int posY[10001]; int cnt; int map[10001][10001]; int ans, minA; int check[10000]; class Queue{ int front, rear; int q[1000000]; public: Queue(); void enQueue(int value); int deQueue(); void reset(); bool is_Empty(); }; Queue::Queue(){ front = rear = -1; } void Queue::enQueue(int value){ q[++rear] = value; } int Queue::deQueue(){ return q[++front]; } bool Queue::is_Empty(){ if(front == rear) return true; return false; } void Queue::reset(){ front = rear = -1; } Queue rQueue, cQueue; int X[8] = {-2, -2, -1, -1, 1, 1, 2, 2}; int Y[8] = {-1, 1, -2, 2, -2, 2, -1, 1}; void BFS(int x){ for(int i = 0 ; i < N; i++){ for(int j = 0; j < M; j++){ visited[i][j] = 0; } } int a = posX[x]; int b = posY[x]; rQueue.reset(); cQueue.reset(); visited[a][b] = 1; rQueue.enQueue(a); cQueue.enQueue(b); while(!rQueue.is_Empty()){ int cr = rQueue.deQueue(); int cc = cQueue.deQueue(); for(int i = 0; i < 8; i++){ int nr = cr + X[i]; int nc = cc + Y[i]; if(nr >= 0 && nr < N && nc >= 0 && nc < M && visited[nr][nc] == 0){ visited[nr][nc] = visited[cr][cc] + 1; rQueue.enQueue(nr); cQueue.enQueue(nc); } } } for(int i = 0; i < cnt; i++){ if(i != x){ int tmpX = posX[i]; int tmpY = posY[i]; map[x][i] = visited[tmpX][tmpY] - 1; map[i][x] = visited[tmpX][tmpY] - 1; } } } void backtrack(int k, int count){ if(minA <= ans){ return; } if(count == cnt){ if(minA > ans){ minA = ans; } return; } for(int i = 1; i < cnt; i++){ if(check[i] == 0 && map[k][i] != 0){ ans += map[k][i]; check[i] = 1; backtrack(i, count + 1); ans -= map[k][i]; check[i] = 0; } } } int main(){ freopen("input.txt", "rt", stdin); cin >> T; for(int tc = 1; tc <= T; tc++){ cin >> N >> M; cnt = 1; for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ cin >> arr[i][j]; if(arr[i][j] == 3){ posX[0] = i; posY[0] = j; } if(arr[i][j] == 1){ posX[cnt] = i; posY[cnt] = j; cnt++; } } } for(int i = 0; i < cnt; i++){ for(int j = 0; j < cnt; j++){ map[i][j] = 0; } } for(int i = 0; i < cnt; i++){ BFS(i); } for(int i = 0; i < cnt; i++){ check[i] = 0; } ans = 0; minA = 1000000; backtrack(0, 1); cout << "Case #" << tc << endl; cout << minA << endl; } return 0; }
Leave a Comment