Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
3.7 kB
7
Indexable
Never
cleaning robot code
#include<iostream>
using namespace std;
int arr[100][100];
int n, m, xR, yR, dirty[10][2], cntD, Answer, step;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int visit[100][100];
int qX[1000000];
int qY[1000000];
int front, rear, sum;
int dist[11][11] = {0};

void push(int x, int y) {
	rear++;
	qX[rear]=x;
	qY[rear]=y;
}
void pop(int &x, int &y) {
	front++;
	x=qX[front];
	y=qY[front];
}
void bfs(int x, int y) {
	front = rear = 0;
	push(x,y);
	while (front < rear) {
		pop(x,y);
		step = visit[x][y];
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 0 && xx < n && yy >= 0 && yy < m) {
				if (visit[xx][yy] == 0) {
					push(xx,yy);
					visit[xx][yy] = step + 1;
				}
			}
		}
	}
}

void backtrack(int k, int start) {
	if (k == cntD) {
		if (sum < Answer) {
			Answer = sum;
		}
		return;
	}
	if (sum >= Answer) return;

	for (int i = 1; i <= cntD; i++) {
		if (dist[i][i] == 0 && i != start) {
			dist[i][i] = 1;
			sum += dist[start][i]; 
			backtrack(k + 1, i);
			dist[i][i] = 0;
			sum -= dist[start][i];
		}
	}
}

int main(int argc, char** argv)
{
	int test_case;
	int T;


	freopen("input.txt", "r", stdin);
	cin >> T;

	for(test_case = 1; test_case <= T; ++test_case)
	{
		step = 0;
		Answer = 1000000;
		cin >> n >> m;
		cntD = 0;
		for (int r = 0; r < n; r++) {
			for (int c = 0; c < m; c++) {
				cin >> arr[r][c];
				visit[r][c] = 0;
				if (arr[r][c] == 3) {
					xR = r;
					yR = c;
				} else if (arr[r][c] == 1) {
					dirty[cntD][0] = r;
					dirty[cntD][1] = c;
					cntD++;
				} else if (arr[r][c] == 2) {
					visit[r][c] = -1;
				}

			}
		}
		for (int i = 0; i <= cntD; i++) {
			for (int j = 0; j <= cntD; j++) {
				dist[i][j] = 0;
			}
		}
		cout << "Case #" << test_case << endl;
		bfs(xR,yR);
		for (int i = 1; i <= cntD; i++) {
			dist[0][i] = visit[dirty[i - 1][0]][dirty[i - 1][1]];
			dist[i][0] = visit[dirty[i - 1][0]][dirty[i - 1][1]];
		}
		for (int i = 1; i <= cntD; i++) {
			if (dist[0][i] == 0) {
				cout << -1 << endl;
				Answer = -1;
				break;
			}
		} 
		if (Answer == -1) {
			continue;
		} else {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (visit[i][j] != -1) {
						visit[i][j] = 0;
					}
				}
			}
			for (int i = 1; i < cntD; i++) {
				step = 0;
				bfs(dirty[i - 1][0],dirty[i - 1][1]);
				for (int j = i + 1; j <= cntD; j++) {
					dist[i][j] = visit[dirty[j - 1][0]][dirty[j - 1][1]];
					dist[j][i] = visit[dirty[j - 1][0]][dirty[j - 1][1]];
				}
				for (int k = 0; k < n; k++) {
					for (int j = 0; j < m; j++) {
						if (visit[k][j] != -1) {
							visit[k][j] = 0;
						}
					}
				}
			}
			sum = 0;
			dist[0][0] = 1;
			backtrack(0, 0);
			cout << Answer << endl;
		}

	}
	return 0;//Your program should return 0 on normal termination.
}


Case #1
38
Case #2
37
Case #3
52
Case #4
-1
Case #5
78
Case #6
43
Case #7
28
Case #8
3
Case #9
54
Case #10
50
Case #11
-1
Case #12
12
Case #13
-1
Case #14
99
Case #15
137
Case #16
117
Case #17
175
Case #18
115
Case #19
132
Case #20
38
Case #21
-1
Case #22
-1
Case #23
140
Case #24
46
Case #25
60
Case #26
56
Case #27
186
Case #28
18
Case #29
140
Case #30
177
Case #31
214
Case #32
207
Case #33
35
Case #34
-1
Case #35
466
Case #36
31
Case #37
228
Case #38
157
Case #39
160
Case #40
120
Case #41
301
Case #42
362
Case #43
272
Case #44
198
Case #45
490
Case #46
83
Case #47
152
Case #48
165
Case #49
333
Case #50
288