Untitled

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




Code:
#include<iostream>
#define max 10000000
using namespace std;
int n,m,h; 
int map[105][105];
int diem_ban[2][15];
int visit[105][105]; // xem diem nao da di qua
int rbi, rbj;
int dx[4]={0, 0, 1, -1};
int dy[4]={1, -1, 0, 0}; 
int queuex[max];
int queuey[max];
int front= -1;
int	rear=-1;
int dis[10000][10000]; // ma tran ke khoang cach giua cac diem ban
int d[10000][10000]; // tinh khoang cach
int check[11];
int cnt;
int tong,kq;
int tiep;
void pushq(int x,int y){
	if(rear == max-1) rear =-1;
	rear++;
	queuex[rear]=x;
	queuey[rear]=y;
}

void pop(){
	if(front == max-1) front =-1;
	front++;

}
bool IsEmpty(){
	return front == rear;
}

bool checkIn(int i ,int j){
	if(i>=0 && i<n && j>= 0 && j<m) return true;
	return false;
}
void resetvisit(){
	for(int i=0; i<n;i++){
			for(int j =0; j< m; j++){
				visit[i][j] =0;
				d[i][j] =0;
			}
	}
}
void resetcheck(){
	for(int i=0; i<h;i++){
		check[i]=0;
	}
}
int bfs(int ibd, int jbd, int iket, int jket){
	front = rear =-1;
	pushq(ibd,jbd);
	resetvisit();
	visit[ibd][jbd] = 1;
	while(!IsEmpty()){
		pop();
		int i1 = queuex[front];
		int j1 = queuey[front];
		for(int k=0; k<4;k++){
			int i2 = i1 + dx[k];
			int j2 = j1 + dy[k];
			if(checkIn(i2,j2)==true && map[i2][j2] != 2 && visit[i2][j2]==0){
				d[i2][j2] = d[i1][j1]+1;
				visit[i2][j2] =1;
				if(i2 == iket && j2 == jket) return d[i2][j2];
				pushq(i2,j2);
			}
		}
	}
	return -1;
}
void backtrack(int  i){
		if(cnt ==h-1) {
			if(kq>tong) kq = tong;
			return;
		}
		int nho = max;

		
		for(int j =1; j< h; j++){
			if(check[j] ==0 && kq>tong ){
				check[j] =1;
				nho =dis[i][j];
				cnt++;
				tong += nho;
				backtrack(j);
				check[j] =0;
				tong -= nho;
				cnt--;

			}
		}
		
}
		

int main(){
	freopen("Text.txt", "r", stdin);
	int test;
	cin >> test;
	for(int tc =1; tc<=test; tc++){
		cin >> n >>m;
		h=1;
		for(int i=0; i<n;i++){
			for(int j =0; j< m; j++){
				cin >> map[i][j];
				if(map[i][j] == 3){
					diem_ban[0][0]=i;
					diem_ban[1][0]=j;
				}
				else if(map[i][j] == 1){
					diem_ban[0][h]=i;
					diem_ban[1][h]=j;
					h++;
				}
			}
		}

		cout << "Case #" << tc << endl;
		tiep =0;
		bool tai =true;
		
		//bfs de tim khoang cach den cac diem ban
		for(int i=0; i<h-1;i++){
					
			if(tai == false) break;
			for(int j =i+1; j< h; j++){
				dis[i][j] = bfs(diem_ban[0][i], diem_ban[1][i], diem_ban[0][j], diem_ban[1][j]);
				if(dis[i][j] == -1){
					tai =false;
					cout << -1<< endl;
					break;
				}

				dis[j][i] = dis[i][j];
				
			}
		}
		if(tai == true){
		cnt =0;
		tong =0;
		kq = max;
		resetcheck();
		check[0] =1;
		backtrack(0);
		cout << kq << endl;
		}

	}
		return 0;
}