Cleaning Robot (thuật toán BFS + BackTracking)

package Advance;

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

public class CleaningRobot {
public static void main(String[] args) throws Exception {
new CleaningRobot().inIt();
}

int M;
int N;
int matrix[][];
Location dirty[];
int numDirty;
int xRB, yRB;
int[][] move = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
MyQueue mQ;
int[][] matrixEnd;
int min;
int visit[];
int Result;

class Location {
int x;
int y;

public Location(int a, int b) {
x = a;
y = b;
}
}

class MyQueue {
Location ele[];
int front;
int rear;

public MyQueue() {
front = rear = 0;
ele = new Location[10001];
}

boolean isEmpty() {
if (front == rear)
return true;
else
return false;
}

void Qpush(Location x) {
ele[rear] = x;
rear++;
if (rear == 10001)
rear = 0;
}

Location Qpop() {
Location a = ele[front];
front++;
if (front == 10001)
front = 0;
return a;
}
}

private void inIt() throws Exception {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int test_case = 1; test_case <= T; test_case++) {
N = sc.nextInt();
M = sc.nextInt();
Result = 0;
numDirty = 1;
matrix = new int[N][M];
dirty = new Location[100];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
matrix[i][j] = sc.nextInt();
if (matrix[i][j] == 3) {
xRB = i;
yRB = j;
dirty[0] = new Location(xRB, yRB);
}
if (matrix[i][j] == 1) {
dirty[numDirty] = new Location(i, j);
numDirty++;
}
}
}
matrixEnd = new int[numDirty][numDirty];
visit = new int[numDirty];
min = 1000000000;
for (int i = 0; i < numDirty - 1; i++) {
for (int j = i + 1; j < numDirty; j++) {
int a = BFS(new Location(dirty[i].x, dirty[i].y),
new Location(dirty[j].x, dirty[j].y));
matrixEnd[i][j] = a - matrix[dirty[i].x][dirty[i].y];
matrixEnd[j][i] = a - matrix[dirty[i].x][dirty[i].y];
if(matrixEnd[i][j] < 0){
matrixEnd[i][j] = -1000000000;
}
}
}
backtrack(0, 0);
if (min > 0) {
Result = min;
} else
Result = -1;
System.out.println("Case #" + test_case);
System.out.println(Result);
}
}

private void backtrack(int num, int total) {
if (total >= min)
return;
if (checkOver()) {
if (total < min) {
min = total;
}
return;
}
for (int j = 0; j < numDirty; j++) {
if (visit[j] == 0) {
visit[j] = 1;
backtrack(j, total + matrixEnd[num][j]);
visit[j] = 0;
}
}
}

private boolean checkOver() {
for (int i = 0; i < numDirty; i++) {
if (visit[i] == 0) {
return false;
}
}
return true;
}

private int BFS(Location start, Location end) {
mQ = new MyQueue();
mQ.Qpush(start);
int temp[][] = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
temp[i][j] = matrix[i][j];
}
}
while (!mQ.isEmpty()) {
Location h = mQ.Qpop();
if (h.x == end.x && h.y == end.y) {
return temp[h.x][h.y];
}
for (int i = 0; i < 4; i++) {
int X = h.x + move[i][0];
int Y = h.y + move[i][1];
if (checkDK(X, Y) && (temp[X][Y] == 0 || temp[X][Y] == 1)) {
temp[X][Y] = temp[h.x][h.y] + 1;
mQ.Qpush(new Location(X, Y));
}
}
}
return 0;
}

private boolean checkDK(int x, int y) {
if (x >= 0 && x < N && y >= 0 && y < M)
return true;
else
return false;
}

}