robot

#include <iostream> #include <conio.h> using namespace std; //Bài toán cleaning robot: tìm số bước đi ngắn nhất để con robot làm sạch hết các ô gạch bẩn int dx[] = {-1,0,0,1}; int dy[] = {0,-1,1,0}; bool visit[300][300]={false},check[11]={false}; int matrix[300][300], kq=1000000,sum_step=0, dis[20][20],n,m,k; struct cell { int x, y; int dis; cell() {} cell(int x, int y, int dis) : x(x), y(y), dis(dis) {} }; cell queue[9000009]; cell dirty[11]; int Vao =0; int Ra = 0; void Init () { Vao = 0; Ra = 0; } cell peek() { return queue[Ra]; } bool isempty() { if(Vao==Ra){ return 1; } return 0; } cell pop() { return queue[Ra++]; } void push( cell x) { queue[Vao++] = x; } bool isInside(int x, int y, int N,int M) { if (x >= 1 && x <= N && y >= 1 && y <= M) return true; return false; } int BFS(int start_x, int start_y,int end_x, int end_y) { Init(); // push starting position of knight with 0 distance push(cell(start_x, start_y, 0)); cell t; int x, y; // make all cell unvisited for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) visit[i][j] = false; // visit starting state visit[start_x][start_y] = true; // loop untill we have one element in queue while (!isempty()) { t = pop(); // if current cell is equal to target cell, // return its distance if (t.x == end_x && t.y == end_y) return t.dis; // loop for all reachable states for (int i = 0; i < 4; i++) { x = t.x + dx[i]; y = t.y + dy[i]; // If reachable state is not yet visited and // inside board, push that state into queue if (isInside(x, y, n, m) && !visit[x][y] && matrix[x][y]!=2) { visit[x][y] = true; push(cell(x, y, t.dis + 1)); } } } return -1; } void backtracking(int count, int parent, int sum){ int i; if(count==k){ if(kq>sum) kq=sum; return; }else { for(i=1;i<k;i++){ if(check[i]==0 && kq>sum){ check[i] = true; count++; backtracking(count, i, sum+dis[parent][i]); check[i] = false; count--; } } } } int main () { ios:: sync_with_stdio(false); int tc,check_move; freopen("input.txt","r", stdin); cin>>tc; for(int t=1;t<=tc;t++){ k=1; check_move = 1; kq = 10000000; //Nhập vào kích thước ma trận cin>>n; cin>>m; //Nhập vào ma trận bản đồ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>matrix[i][j]; if(matrix[i][j]==3){ //Lưu lại vị trí con robot dirty[0].x = i; dirty[0].y = j; }else if(matrix[i][j]==1){ //Lưu lại vị trí các ô gạch bẩn dirty[k].x = i; dirty[k].y = j; k++; } } } cout<<"Case #"<<t<<endl; //Dùng BFS tính trước ma trận khoảng cách ngắn nhất giữa các đỉnh for(int i=0;i<k;i++){ for(int j=0;j<k;j++){ if(i<j && check_move==1){ dis[i][j] = BFS(dirty[i].x, dirty[i].y, dirty[j].x, dirty[j].y); dis[j][i] = dis[i][j]; if(dis[j][i] == -1) { cout<<"-1"<<endl; check_move = 0; break; } } } } //Dùng backtracking để tìm thứ tự đi đến các ô gạch bẩn sao cho đường đi là ngắn nhất if(check_move==1){ for(int i=1;i<k;i++){ check[i] = false; } backtracking(1, 0, 0); cout<<kq<<endl; } } getch(); return 0; }