# Untitled

unknown
plain_text
24 days ago
3.1 kB
0
Indexable
Never
```public class Solution {
static int[][] map;
static PointCs[] dirtys;
static int MAX_DIRTY = 12;
static int totalDirty = 0;
static Queue<PointCs> qt;
static int[] visited;
static int[][] step;
static int[][] adj;

static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, 1, 0, -1 };

public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);

int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
int n = sc.nextInt();
int m = sc.nextInt();

int xR = 0, yR = 0;

totalDirty = 0;
qt = new Queue<Solution.PointCs>();

map = new int[n][m];
step = new int[n][m];

dirtys = new PointCs[MAX_DIRTY];
visited = new int[MAX_DIRTY];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
map[i][j] = sc.nextInt();
if (map[i][j] == 1) {
totalDirty++;
dirtys[totalDirty] = new PointCs(i, j);
} else if (map[i][j] == 3) {
xR = i;
yR = j;
}
}
}

adj = new int[totalDirty + 1][totalDirty + 1];
bfs(xR, yR);

boolean canNotGoDirty = false;
PointCs diryCs;
for (int i = 1; i <= totalDirty; i++) {
for (int j = i + 1; j <= totalDirty; j++) {
if (step[i][j] != 0) {
adj[i][j] = step[i][j] - 1;
adj[j][i] = step[i][j] - 1;
} else {
adj[i][j] = step[i][j] - 1;
adj[j][i] = step[i][j] - 1;
canNotGoDirty = true;
}
}
}

if (canNotGoDirty) {
System.out.println(-1);
} else {

}

//			for (int i = 0; i < step.length; i++) {
//				System.out.println(Arrays.toString(step[i]));
//			}
//			System.out.println();

dirtys = null;
adj = step = map = null;
visited = null;
qt = null;
}
sc.close();
}

private static void bfs(int x, int y) {
qt.reset();
qt.enQueue(new PointCs(x, y));
step[x][y] = 1;

PointCs tmpPoint;
while (!qt.isEmpty()) {
tmpPoint = qt.peek();
qt.deQueue();

for (int i = 0; i < 4; i++) {
int xx = tmpPoint.x + dx[i];
int yy = tmpPoint.y + dy[i];
if (isSafe(xx, yy)) {
if (step[xx][yy] == 0) {
step[xx][yy] = step[tmpPoint.x][tmpPoint.y] + 1;
qt.enQueue(new PointCs(xx, yy));
}
}
}
}

int robot = 0;
PointCs dirtyCs;
for (int i = 1; i <= totalDirty; i++) {
dirtyCs = dirtys[i];
if (step[dirtyCs.x][dirtyCs.y] != 0) {
adj[robot][i] = step[dirtyCs.x][dirtyCs.y] - 1;
adj[i][robot] = step[dirtyCs.x][dirtyCs.y] - 1;
} else {
adj[robot][i] = -1;
adj[i][robot] = -1;
}
}

for (int i = 0; i < step.length; i++) {
System.out.println(Arrays.toString(step[i]));
}
System.out.println();

for (int i = 0; i < adj.length; i++) {
System.out.println(Arrays.toString(adj[i]));
}
System.out.println();
}

private static boolean isSafe(int xx, int yy) {
if (xx >= 0 && xx < map.length && yy >= 0 && yy < map[0].length) {
if (map[xx][yy] != 2) {
return true;
}
}

return false;
}```
Leave a Comment