Untitled
unknown
plain_text
2 years ago
2.4 kB
7
Indexable
#include<iostream> using namespace std; int dx[8] = {-1, -2, -1, -2, 1, 2, 1, 2}; int dy[8] = {-2, -1, 2, 1, 2, 1, -2, -1}; int QX[1000000], QY[1000000]; int visit[105][105]; int N, M; int A[105][105]; int toadodichX[100], toadodichY[100]; int counting[105][105]; int map[105][105]; int cntDich; int dust[105][105]; int Answer; int visitDich[100]; void reset() { for(int i = 0;i < N;i++) { for(int j = 0;j < M;j++) { visit[i][j] = 0; counting[i][j] = 0; } } }; void BFS(int a, int b, int start) { reset(); int front = 0, rear = 0; QX[rear] = a; QY[rear] = b; rear++; visit[a][b] = 1; counting[a][b] = 0; while(front != rear) { int tempx = QX[front]; int tempy = QY[front]; front++; for(int i = 0;i < 8;i++) { int xx = tempx + dx[i]; int yy = tempy + dy[i]; if(xx >= 0 && xx < N && yy >= 0 && yy < M && visit[xx][yy] == 0) { visit[xx][yy] = 1; QX[rear] = xx; QY[rear] = yy; rear++; counting[xx][yy] = counting[tempx][tempy] + 1; if(A[xx][yy] == 1) { map[start][dust[xx][yy]] = counting[xx][yy]; } else if(A[xx][yy] == 3) { map[start][dust[xx][yy]] = counting[xx][yy]; } } } } //cout << endl; } void backstrack(int idxdich, int sum, int dem) { if(dem == cntDich-1) { if(Answer > sum) { Answer = sum; } return; } for(int i = 1; i < cntDich;i++) { if(visitDich[i] == 0) { visitDich[i] = 1; backstrack(i, sum + map[idxdich][i], dem+1); visitDich[i] = 0; } } } int main(int argc, char** argv) { int test_case; int T; ios::sync_with_stdio(false); freopen("input.txt", "r", stdin); cin >> T; for(test_case = 1; test_case <= T; ++test_case) { Answer = 9999; cntDich = 1; cin >> N >> M; reset(); for(int i = 0;i < N;i++) { for(int j = 0;j < M;j++) { cin >> A[i][j]; if(A[i][j] == 1) { toadodichX[cntDich] = i; toadodichY[cntDich] = j; dust[i][j] = cntDich; cntDich++; } else if(A[i][j] == 3) { toadodichX[0] = i; toadodichY[0] = j; dust[i][j] = 0; } } } for(int i = 0; i < cntDich;i++) { visitDich[i] = 0; BFS(toadodichX[i], toadodichY[i], i); } backstrack(0, 0, 0); cout << "Case #" << test_case << endl << Answer << endl; } return 0; }
Editor is loading...