# Untitled

unknown
plain_text
a year ago
3.7 kB
1
Indexable
Never
```#include <iostream>

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;
}```