package practice;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
/*
* http://www.hoangvancong.com/2016/10/28/bfs-backtrack-robot-don-dep-cleaning-robot/
* hoán vị các trường hợp lau gạch rồi cắt tỉa BFS
*/
public class ClearningRobot {
Scanner sc = new Scanner(System.in);
int t, n, m, st, en, L, answer;
int map[][];
int visit[][];
int queueX[];
int queueY[];
int vertex[][];
int adj[][];
int visitHoanVi[];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
void init() {
visitHoanVi = new int[n*m];
queueX = new int[1000000];
queueY = new int[1000000];
answer = 100000;
adj = new int[n * m][n * m];
vertex = new int[n * m][2];
L = 1;
st = en = 0;
map = new int[n + 1][m + 1];
visit = new int[n + 1][m + 1];
}
void initVisit() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
visit[i][j] = -1;
}
}
}
void BFS(int startX, int startY) {
queueX[en] = startX;
queueY[en] = startY;
en++;
visit[startX][startY] = 0;
while (st != en) {
int x = queueX[st];
int y = queueY[st];
st++;
for (int i = 0; i < 4; i++) {
int xNext = x + dx[i];
int yNext = y + dy[i];
if (xNext >= 0 && xNext < n && yNext >= 0 && yNext < m) {
if (visit[xNext][yNext] == -1) {
if (map[xNext][yNext] != 2) {
queueX[en] = xNext;
queueY[en] = yNext;
en++;
visit[xNext][yNext] = visit[x][y] + 1;
}
}
}
}
}
}
// 5<=n,m<=100
// vấn đề của mình muôn thuở vẫn là đệ quy, quay lui (backtracking)
/*
void solve(int index, int last, int sum) {
// ans max nhất cũng chỉ = (10^4)-1(1 là robot đứng) vì n,m<=100 nên vượt qua
// 10^4 thì sai ngay
if (sum >= answer) {
return;
}
// đi hết các vị trí có gạch bẩn rồi thì answer chính là tổng số bước đi
if (index == L) {
answer = sum;
return;
}
visitHoanVi = new int[n*m];
// vị trí i==0 robot đứng rồi nên xét i chạy từ 1
for (int i = 1; i < L; i++) {
if (visitHoanVi[i] == 0 && adj[last][i] != -1) {
visitHoanVi[i] = 1;
solve(index + 1, i, sum + adj[last][i]);
visitHoanVi[i] = 0;
}
}
}
*/
void solve(int idx, int last, int sum) {
// nếu kết quả truyền vào ở hàm solve(idx+1, i, sum + adj[last][i]);
// sum chính là sum + adj[last][i] lúc này mà lớn hơn kết quả trước thì return ngay vì mình đang cần tìm số bước đi nhỏ nhất hay khoảng cách nhỏ nhất
// vẽ hình ra là thấy rõ được cái hàm này
if (sum >= answer)
return;
// nếu đến hoán vị cuối cùng thì cập nhật kết quả Ans và dừng lại
if (idx == L) {
answer = sum;
return;
}
// chú ý lỗi sai visitHoanVi [][] ở dưới vì mỗi lần sinh hoán vị ta lại reset nó làm mất đi các hoán vị đã xét rồi chả hạn nên ko có đủ các cấu hình để so sánh
//visitHoanVi = new int[n*m];
for (int i = 1; i < L; i++) {
// thứ tự hoán vị chưa được visit và visit mảng adj (khoảng cách)
if (visitHoanVi[i]==0 && adj[last][i] != -1) {
visitHoanVi[i] = 1;
solve(idx + 1, i, sum + adj[last][i]);
visitHoanVi[i] = 0;
}
}
}
void solution() {
t = sc.nextInt();
for (int tc = 1; tc <= t; tc++) {
n = sc.nextInt();
m = sc.nextInt();
init();
initVisit();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
map[i][j] = sc.nextInt();
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] == 3) {
vertex[0][0] = i;
vertex[0][1] = j;
}
else if (map[i][j] == 1) {
vertex[L][0] = i;
vertex[L][1] = j;
// do L++ nên ở dưới ta chỉ cần xét tới L-1, chứ ko cần xét tới L
// Quy tắc đệ quy thường là từ 0 tới n || từ 1 tới (n+1)
L++;
}
}
}
// System.out.println(“vertex[][]”);
// for(int i=0; i<L; i++) {
// for(int j=0; j<2; j++) {
// System.out.print(vertex[i][j]+” “);
// }
// System.out.println();
// }
for (int i = 0; i < L; i++) {
initVisit();
BFS(vertex[i][0], vertex[i][1]);
for (int j = 0; j < L; j++) {
adj[i][j] = visit[vertex[j][0]][vertex[j][1]];
}
}
// System.out.println(“adj[][]”);
// for(int i=0; i<L; i++) {
// for(int j=0; j<L; j++) {
// System.out.print(adj[i][j]+” “);
// }
// System.out.println();
// }
// vẽ ma trận adj[][] ra là thấy
// bắt đầu từ đỉnh 0 đi tới đỉnh 1 vs tổng ban đầu là 0
// solve(1, 0, 0);
// if (answer == 100000) {
// answer = -1;
// }
answer = 1000000;
solve(1, 0, 0);
if (answer == 1000000) answer = -1;
System.out.println(“Case #” + tc);
System.out.println(answer);
}
}
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream(“ClearningRobot.txt”));
ClearningRobot c = new ClearningRobot();
c.solution();
}
}
alexishuuuocn 