Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.4 kB
4
Indexable
Never
#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;
}