# Untitled

unknown
plain_text
a year ago
3.0 kB
2
Indexable
Never
```package Cleaning_Robot;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
static int n, m, res;
static int[][] a = new int[105][105], kc;
static int x, y;
static int[] xdirty = new int[15], ydirty = new int[15], visit, hvi;
static int dirty, tuong;
static int[] dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 };
static int[] qx = new int[10005], qy = new int[10005];

public static void BFS(){
for(int i = 0; i < dirty-1; i++){
int[][] lan = new int[n][m];
int[][] visit = new int[n][m];

int front = 0, rear = 0;
qx[front] = xdirty[i]; qy[front] = ydirty[i];
lan[xdirty[i]][ydirty[i]] = 0;
visit[xdirty[i]][ydirty[i]] = 1;
while(front <= rear){
int x = qx[front];
int y = qy[front];
int c = lan[x][y];

for(int j = 0; j < 4; j++){
int nx = x + dx[j];
int ny = y + dy[j];
if(nx >= 0 && ny >= 0 && nx < n && ny < m && a[nx][ny] != 2 && visit[nx][ny] == 0){
rear++;
qx[rear] = nx;
qy[rear] = ny;
lan[nx][ny] = c+1;
visit[nx][ny] = 1;
}
}

front++;
}
for(int j = i+1; j < dirty; j++){
kc[i][j] = lan[xdirty[j]][ydirty[j]];
kc[j][i] = lan[xdirty[j]][ydirty[j]];
}

}
}

public static boolean cant(){
for(int i = 0; i < dirty; i++){
for(int j = 0; j < dirty; j++){
if(i != j && kc[i][j]==0){
return true;
}
}
}
return false;
}

public static void backTrack(int k, int length) {
if(length >= res){
return;
}
if(k==dirty){
res = Math.min(res, length);
return;
}
for(int i = 1; i < dirty; i++){
if(visit[i] == 0){
hvi[k] = i;
visit[i] = 1;
int distan = kc[hvi[k]][hvi[k-1]];
backTrack(k+1, length+distan);
visit[i] = 0;
}
}
}

public static void main(String[] args) {
try {
System.setIn(new FileInputStream("input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Scanner scanner = new Scanner(System.in);
int test = scanner.nextInt();
for (int t = 1; t <= test; t++) {
n = scanner.nextInt();
m = scanner.nextInt();
dirty = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
a[i][j] = scanner.nextInt();
if (a[i][j] == 3) {
xdirty[dirty] = i;
ydirty[dirty] = j;
dirty++;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == 1) {
xdirty[dirty] = i;
ydirty[dirty] = j;
dirty++;
}
}
}
res = Integer.MAX_VALUE;

visit = new int[dirty];
hvi = new int[dirty];
kc = new int[dirty][dirty];
BFS();

if(cant()){
System.out.println("Case #" + t + "\n-1");
}else{
backTrack(1, 0);
System.out.println("Case #" + t + "\n" + res);
}

}
scanner.close();
}
}
```