Untitled
unknown
plain_text
21 days ago
3.1 kB
2
Indexable
Never
#include <iostream> using namespace std; int T, N, M; int arr[105][105]; int posX[11]; int posY[11]; int visited[105][105]; int map[11][11]; int k; int ans, minA; int x, y; 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]; } void Queue::reset(){ front = rear = -1; } bool Queue::is_Empty(){ if(front == rear) return true; return false; } int X[4] = {-1, 1, 0, 0}; int Y[4] = {0, 0, 1, -1}; int check[11]; Queue rQueue, cQueue; int init[105][105]; int cnt; void backtrack(int n, int tmp){ if(ans >= minA){ return; } if(tmp == k){ if(ans < minA) minA = ans; return; } for(int i = 1; i < k; i++){ if(map[n][i] != 0 && check[i] == 0 ){ ans += map[n][i]; check[i] = 1; backtrack(i, tmp + 1); ans -= map[n][i]; check[i] = 0; } } } void BFS(int x, int y){ int a = posX[x]; int b = posY[x]; int c = posX[y]; int d = posY[y]; for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ visited[i][j] = 0; init[i][j] = arr[i][j]; } } rQueue.reset(); cQueue.reset(); init[a][b] = 0; visited[a][b] = 1; rQueue.enQueue(a); cQueue.enQueue(b); int flag; while(rQueue.is_Empty() == false){ flag = 0; int x1 = rQueue.deQueue(); int y1 = cQueue.deQueue(); for(int i = 0; i < 4; i++){ int row = x1 + X[i]; int col = y1 + Y[i]; if(row >= 0 && row < N && col >= 0 && col < M && visited[row][col] == 0 && init[row][col] != 2){ if(row == c && col == d){ init[row][col] = init[x1][y1] + 1; map[x][y] = init[row][col]; map[y][x] = init[row][col]; flag = 1; break; }else{ init[row][col] = init[x1][y1] + 1; visited[row][col] = 1; rQueue.enQueue(row); cQueue.enQueue(col); } } if(flag == 1){ break; } } if(flag == 1){ break; } } if(init[c][d] == -1 || init[c][d] == -3){ map[x][y] = 0; map[y][x] = 0; } } int main(){ freopen("input.txt", "rt", stdin); cin >> T; for(int tc = 1; tc <= T; tc++){ cin >> N >> M; for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ cin >> arr[i][j]; if(arr[i][j] == 3){ x = i; y = j; arr[i][j] = -3; } } } posX[0] = x; posY[0] = y; k = 1; for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ if(arr[i][j] == 1){ arr[i][j] = -1; posX[k] = i; posY[k] = j; k++; } } } for(int i = 0; i < k - 1; i++){ for(int j = i + 1; j < k; j++){ BFS(i, j); } } for(int i = 0; i < k; i++){ check[i] = 0; } ans = 0; minA = 1000000; backtrack(0, 1); cout << "Case #" << tc << endl; if(minA == 1000000){ cout << -1 << endl; }else{ cout << minA << endl; } } while(1); return 0; }
Leave a Comment