Cleaning Robot

avatar
quoc14
c_cpp
5 months ago
6.0 kB
8
Indexable
Backtrack
Level 4
Cleaning Robot
We have to plan a path for a cleaning robot to clean a rectangular room floor of size NxM. The room floor paved with square tiles whose size fits the cleaning robot (1 × 1). There are clean tiles and dirty tiles, and the robot can change a dirty tile to a clean tile by visiting the tile. Also there may be some obstacles (furniture) whose size fits a tile in the room. If there is an obstacle on a tile, the robot cannot visit it. The robot moves to an adjacent tile with one move. The tile onto which the robot moves must be one of four tiles (i.e., east, west, north or south) adjacent to the tile where the robot is present. The robot may visit a tile twice or more.

Your task is to write a program which computes the minimum number of moves for the robot to change all dirty tiles to clean tiles, if ever possible.

Time limit: 1s (C/C++), 2s (Java)

Submit limit: 10 times

Example:

The following is a room of size 5x7, with 3 dirty tiles, and 0 furniture. The answer for this case is 8.


Input

The input consists of multiple maps, the first line is the number of test case T (T < = 50).

Each test case begins with N and M representing the size of the room. ( 5 =< N, M <= 100)

The next N line representing the arrangement of the room with following describe:

0 : a clean tile
1 : a dirty tile
2 : a piece of furniture (obstacle)
3 : the robot (initial position)

In the map the number of dirty tiles does not exceed 10 and there is only one robot.

Output

Print each test case on two lines, the first line of each test case is "Case #x", where x is the test case number. The next line is the minimum number of moves for the robot to change all dirty tiles to clean tiles. If the map includes dirty tiles which the robot cannot reach, your program should output -1.

Sample

Input

5
5 7
0 0 0 0 0 0 0
0 3 0 0 0 1 0
0 0 0 0 0 0 0
0 1 0 0 0 1 0
0 0 0 0 0 0 0
5 15
0 0 0 0 2 0 2 0 0 0 0 1 2 0 1
0 0 0 1 0 2 0 2 2 0 1 2 0 0 0
2 1 0 2 0 1 0 2 0 0 0 0 0 0 0
0 0 0 1 0 2 0 0 1 2 0 0 2 0 0
0 2 1 0 2 0 0 0 0 0 3 0 0 0 0

...............

Output

Case #1
8
Case #2
38
Case #3
37
Case #4
-1
Case #5
49

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
Time: 1.156000000 s.

#include <iostream>
#include <time.h>
using namespace std;

int oo = 2000000000;

int T, n, m, result, mp[101][101];
int xx1, yy1, p, step[11][11], point[11][2];

bool vs[101][101], bt[11], noDir;
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };

int arr[40001][3];
int head, tail;

void init(){
	head = 0, tail = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++) vs[i][j] = false;
	}
}

void push(int x, int y, int cnt){
	arr[tail][0] = x, arr[tail][1] = y, arr[tail++][2] = cnt;
}

void pop(){ head++; }

bool isEmpty(){ return head == tail; }

int getX(){ return arr[head][0]; }

int getY(){ return arr[head][1]; }

int getC(){ return arr[head][2]; }


// 0:left, 1:right, 2:down, 3:up
void bfs(int i_start, int i_stop){
	init();
	int x_start = point[i_start][0];
	int y_start = point[i_start][1];
	int x_stop = point[i_stop][0];
	int y_stop = point[i_stop][1];

	push(x_start, y_start, 0);
	vs[x_start][y_start] = true;
	
	while(!isEmpty()){
		int x = getX();
		int y = getY();
		int c = getC();

		pop();
		if(x == x_stop && y == y_stop){
			step[i_start][i_stop] = c;
			step[i_stop][i_start] = c;
			return;
		}

		for(int dir = 0; dir < 4; dir++){
			int xx = x + dx[dir];
			int yy = y + dy[dir];
			if(xx >= 0 && xx < n && yy >= 0 && yy < m 
				&& mp[xx][yy] != 2 && !vs[xx][yy]){
				vs[xx][yy] = true;
				push(xx, yy, c+1);
			}
		}

	}
}

void backtracking(int index, int cnt, int cntStep){
	if(cnt == p){
		if(cntStep < result) result = cntStep;
		return;
	} else if(result < cntStep){
		return;
	}	
	for(int i = 1; i < p; i++){
		if(!bt[i]){
			cntStep += step[index][i];
			bt[i] = true;
			backtracking(i, cnt+1, cntStep);
			cntStep -= step[index][i];
			bt[i] = false;
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);

	// Calc clock
	
	clock_t time_start, time_end; 
	time_start = clock(); 
	

	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		// Initial && Input
		p = 1, result = oo, noDir = false;
		for(int i = 0; i < p; i++) bt[i] = false;

		cin >> n >> m;
		for(int i = 0; i < n; i++){
			for(int j =0; j < m; j++){
				cin >> mp[i][j];
				if(mp[i][j] == 3){
					xx1 = i, yy1 = j;
					point[0][0] = i, point[0][1] = j; 
					step[0][0] = 0;
				} else if(mp[i][j] == 1){
					point[p][0] = i, point[p][1] = j; 
					step[p][p] = 0;
					p++;
				}
			}
		}
		
		
		// Solve Problem
		// Sinh ma tran ke
		for(int i = 0; i < p-1; i++){
			for(int j = i+1; j < p; j++){
				step[i][j] = oo, step[j][i] = oo;
				bfs(i, j);
				if(step[i][j] == oo) noDir = true;
			}
		}

		// Solve Probblem
		if(noDir){
			cout << "Case #" << tc << endl << -1 << endl;
		} else{
			bt[0] = true;
			backtracking(0, 1, 0);
			cout << "Case #" << tc << endl << result << endl;
		}
	}

	// Calc Time
	
	time_end = clock();
	cout.setf(ios::fixed);
	cout.precision(9);
	cout << "Time: " << double (time_end - time_start) / double (CLOCKS_PER_SEC) << " s." << endl;
	
	return 0;
 }
Leave a Comment