1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
class Solution {
construct2DGrid(edges: number[][]): number[][] {
let n = 0;
for (const [u, v] of edges) n = Math.max(n, u, v);
n++;
const g: number[][] = Array.from({length: n}, () => []);
for (const [u, v] of edges) {
g[u].push(v);
g[v].push(u);
}
const pos2node = new Map<string, number>();
const node2pos = new Map<number, [number, number]>();
const used = new Set<string>();
const q: [number, number][] = [[0, 0]];
node2pos.set(0, [0, 0]);
pos2node.set('0,0', 0);
used.add('0,0');
const dr = [0, 0, 1, -1], dc = [1, -1, 0, 0];
while (q.length) {
const [r, c] = q.shift()!;
const u = pos2node.get(`${r},${c}`)!;
for (const v of g[u]) {
if (node2pos.has(v)) continue;
for (let d = 0; d < 4; d++) {
const nr = r + dr[d], nc = c + dc[d];
const key = `${nr},${nc}`;
if (!used.has(key)) {
node2pos.set(v, [nr, nc]);
pos2node.set(key, v);
used.add(key);
q.push([nr, nc]);
break;
}
}
}
}
let minr = Infinity, maxr = -Infinity, minc = Infinity, maxc = -Infinity;
for (const [_, [r, c]] of node2pos) {
minr = Math.min(minr, r);
maxr = Math.max(maxr, r);
minc = Math.min(minc, c);
maxc = Math.max(maxc, c);
}
const rows = maxr - minr + 1, cols = maxc - minc + 1;
const grid: number[][] = Array.from({length: rows}, () => Array(cols).fill(-1));
for (const [node, [r, c]] of node2pos) {
grid[r - minr][c - minc] = node;
}
return grid;
}
}
|