Untitled
unknown
plain_text
2 years ago
3.8 kB
23
Indexable
import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class CleaningRobot { static int n, m; static int a[][]; static int dx[] = { 0, 0, 1, -1 }; static int dy[] = { 1, -1, 0, 0 }; static int Qx[]; static int Qy[]; static int visit[][], visitVetBan[]; static int d[][]; static int xRobot, yRobot; static int cbiData[][]; static int vetBanX[]; static int vetBanY[]; static int VetBan; static int ans; public static void main(String[] args) { try { System.setIn(new FileInputStream("RoBot")); } catch (FileNotFoundException e) { e.printStackTrace(); } Scanner sc = new Scanner(System.in); int numTest = sc.nextInt(); for (int tc = 1; tc <= numTest; tc++) { n = sc.nextInt(); m = sc.nextInt(); a = new int[n + 2][m + 2]; VetBan = 0; vetBanX = new int[11]; vetBanY = new int[11]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { a[i][j] = sc.nextInt(); if (a[i][j] == 3) { // xRobot = i; // yRobot = j; vetBanX[0] = i; // luu robot vetBanY[0] = j; } if (a[i][j] == 1) { VetBan++; vetBanX[VetBan] = i; vetBanY[VetBan] = j; } } } cbiData = new int[100][100]; chuanBiDuLieu(); boolean checkDonSachPhong = true; for (int i = 0; i <= VetBan; i++) { // int sumDong = 0; for (int j = 0; j <= VetBan; j++) { sumDong += cbiData[i][j]; } if (sumDong == 0) { checkDonSachPhong = false; break; } } System.out.println("Case #" + tc); if (!checkDonSachPhong) System.out.println("-1"); else { ans = 1000000000; visitVetBan = new int[11]; backTrack(0, 0, 0); System.out.println(ans); } } } public static void chuanBiDuLieu() { for (int i = 0; i < VetBan; i++) { for (int j = i + 1; j <= VetBan; j++) { int data = BFS(vetBanX[i], vetBanY[i], vetBanX[j], vetBanY[j]); cbiData[i][j] = data; cbiData[j][i] = data; } } // for (int i = 0; i <= VetBan; i++) { // for (int j = 0; j <= VetBan; j++) { // System.out.print(cbiData[i][j] + " "); // } // System.out.println(); // } } public static void backTrack(int vetBanThux, int sum, int numVetBan) { if (numVetBan == VetBan) { ans = Math.min(ans, sum); return; } for (int i = 1; i <= VetBan; i++) { // tung vi tri trong hang if (visitVetBan[i] == 0) { visitVetBan[i] = 1; backTrack(i, sum + cbiData[vetBanThux][i], numVetBan + 1); visitVetBan[i] = 0; } } } public static int BFS(int x, int y, int vetBanxX, int vetBanxY) { Qx = new int[n * m]; Qy = new int[n * m]; visit = new int[n + 2][m + 2]; d = new int[n + 2][m + 2]; int front = 0; int rear = 0; Qx[rear] = x; Qy[rear] = y; rear++; visit[x][y] = 1; while (front != rear) { int tmpx = Qx[front]; int tmpy = Qy[front]; front++; for (int i = 0; i < 4; i++) { int xx = tmpx + dx[i]; int yy = tmpy + dy[i]; if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && visit[xx][yy] == 0) { if (a[xx][yy] != 2) { d[xx][yy] = d[tmpx][tmpy] + 1; visit[xx][yy] = 1; Qx[rear] = xx; Qy[rear] = yy; rear++; } if (xx == vetBanxX && yy == vetBanxY) { d[xx][yy] = d[tmpx][tmpy] + 1; return d[xx][yy]; } } } } // for (int i = 1; i <= n; i++) { // for (int j = 1; j <= m; j++) { // System.out.print(d[i][j] + " "); // } // System.out.println(); // } // // System.out.println(); // System.out.println(); return 0; } }
Editor is loading...