Untitled
unknown
plain_text
a month ago
4.3 kB
3
Indexable
Never
#include<iostream> using namespace std; #define MAXSIZE 101 #define MAXQUEUE 10100 class Queue { int head, rear; int A[MAXQUEUE]; public: Queue(); ~Queue(); void enQueue(int inS); int deQueue(); bool is_Empty(); void reset(); private: }; Queue::Queue() { head = rear = -1; } Queue::~Queue() { } void Queue::enQueue(int inS){ A[++rear] = inS; } int Queue::deQueue(){ return A[++head]; } bool Queue::is_Empty(){ if(head == rear) return true; return false; } void Queue::reset(){ head = rear = -1; } int Map[101][101]; int visited[101][101]; int dist[11][11]; int rDirty[11], cDirty[11], node[11]; int nTestcase, N, M, nDirty, rStart, cStart, Min, step, cnt, nr, nc, rr, cc, sum; int rspin[4] = {-1,1,0,0}; int cspin[4] = {0,0,-1,1}; Queue rQueue, cQueue; void resetVisit(){ for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ visited[i][j] = -1; } } } int total(){ int temp = 0; for(int i = 0; i < nDirty; i++){ temp += node[i]; } return temp; } void backtrack(int dirty, int nD){ if(step >= Min) return; if(nD == nDirty){ Min = Min > step ? step : Min; return; } for(int i = 1; i < nDirty; i++){ if(dist[dirty][i] != 0 && node[i] == 0){ node[i]++; step += dist[dirty][i]; /*sum = total(); if(sum == nDirty){ Min = Min > step ? step : Min; node[i]--; step -= dist[dirty][i]; return; }*/ backtrack(i, nD + 1); node[i]--; step -= dist[dirty][i]; } } } void BFS(int r, int c){ cnt = 0; rQueue.reset(); cQueue.reset(); rQueue.enQueue(r); cQueue.enQueue(c); visited[r][c]++; while(rQueue.is_Empty() == false && cnt < nDirty + 1){ rr = rQueue.deQueue(); cc = cQueue.deQueue(); for(int i = 0; i < 4; i++){ nr = rr + rspin[i]; nc = cc + cspin[i]; if(nr >= 0 && nr < N && nc >= 0 && nc < M && Map[nr][nc] != 2){ if(visited[nr][nc] == -1){ if(Map[nr][nc] == 1) cnt++; visited[nr][nc] = visited[rr][cc] + 1; rQueue.enQueue(nr); cQueue.enQueue(nc); }else if(visited[nr][nc] > visited[rr][cc] + 1){ visited[nr][nc] = visited[rr][cc] + 1; } } } } } int main(){ freopen("input.txt","r",stdin); cin >> nTestcase; for(int testcase = 1; testcase <= nTestcase; testcase++){ cin >> N >> M; nDirty = 1; for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ cin >> Map[i][j]; visited[i][j] = -1; if(Map[i][j] == 1 || Map[i][j] == 3){ if(Map[i][j] == 1){ rDirty[nDirty] = i; cDirty[nDirty] = j; nDirty++; }else{ rDirty[0] = i; cDirty[0] = j; } } } } bool check = true; for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ if(Map[i][j] == 1){ int temp = 0; if((i == 0 && j == 0) || (i == 0 && j == M - 1) || (i == N - 1 && j == 0) || (i == N - 1 && j == M -1)){ for(int k = 0; k < 4; k++){ nr = i + rspin[k]; nc = j + cspin[k]; if(nr >= 0 && nr < N && nc >= 0 && nc < M && Map[nr][nc] == 2) temp++; } if(temp == 2) check = false; break; }else if(i == 0 || j == 0 || i == N - 1 || j == M - 1){ for(int k = 0; k < 4; k++){ nr = i + rspin[k]; nc = j + cspin[k]; if(nr >= 0 && nr < N && nc >= 0 && nc < M && Map[nr][nc] == 2) temp++; } if(temp == 3) check = false; break; }else{ for(int k = 0; k < 4; k++){ nr = i + rspin[k]; nc = j + cspin[k]; if(nr >= 0 && nr < N && nc >= 0 && nc < M && Map[nr][nc] == 2) temp++; } if(temp == 4) check = false; break; } } } } if(check == false){ cout << "Case #" << testcase << endl << -1 << endl; }else{ Min = 100000000; step = cnt = 0; for(int i = 0; i < nDirty; i++){ resetVisit(); BFS(rDirty[i],cDirty[i]); for(int j = 0; j < nDirty; j++){ dist[i][j] = visited[rDirty[j]][cDirty[j]]; } node[i] = 0; } node[0] = 1; backtrack(0,1); cout << "Case #" << testcase << endl << Min << endl; } } return 0; }