1var assert = require('assert');
2
3function floodFill(matrix, row, col, newVal) {
4  if (matrix[row][col] == newVal) {
5    return matrix;
6  }
7  replaceWithMatch(matrix[row][col], matrix, row, col, newVal);
8  return matrix;
9}
10
11function replaceWithMatch(match, matrix, r, c, newVal) {
12  if (matrix[r] && matrix[r][c] >= 0 && matrix[r][c] == match) {
13    matrix[r][c] = newVal;
14    if (matrix[r - 1]) {
15      // when there is no left neighbor
16      replaceWithMatch(match, matrix, r - 1, c, newVal);
17    }
18    replaceWithMatch(match, matrix, r, c - 1, newVal);
19    if (matrix[r + 1]) {
20      replaceWithMatch(match, matrix, r + 1, c, newVal);
21    }
22    replaceWithMatch(match, matrix, r, c + 1, newVal);
23  }
24}
25
26const input = [
27  [1, 1, 1, 1, 1, 1, 1],
28  [1, 1, 1, 1, 1, 1, 0],
29  [1, 0, 0, 1, 1, 0, 1],
30  [1, 2, 1, 2, 1, 2, 0],
31  [1, 2, 1, 2, 2, 2, 0],
32  [1, 2, 2, 2, 1, 2, 0],
33  [1, 1, 1, 1, 1, 2, 1],
34];
35
36console.log(floodFill(input, 0, 0, 3));
37
38class Graph {
39  constructor() {
40    this.adjacencyList = new Map();
41    this.verticesCount = 0;
42  }
43
44  addVertex(nodeVal) {
45    this.adjacencyList.set(nodeVal, []);
46    this.verticesCount++;
47  }
48
49  addEdge(src, dest) {
50    this.adjacencyList.get(src).push(dest);
51    this.adjacencyList.get(dest).push(src);
52    // push to both adjacency lists
53  }
54
55  removeVertex(val) {
56    if (this.adjacencyList.get(val)) {
57      this.adjacencyList.delete(val);
58    }
59
60    this.adjacencyList.forEach((vertex) => {
61      const neighborIdx = vertex.indexOf(val);
62      if (neighborIdx >= 0) {
63        vertex.splice(neighborIdx, 1);
64      }
65    });
66  }
67
68  removeEdge(src, dest) {
69    const srcDestIdx = this.adjacencyList.get(src).indexOf(dest);
70    this.adjacencyList.get(src).splice(srcDestIdx, 1);
71
72    const destSrcIdx = this.adjacencyList.get(dest).indexOf(src);
73    this.adjacencyList.get(dest).splice(destSrcIdx, 1);
74  }
75
76  printNeighbors() {
77    const result = [];
78
79    for (let vertex of this.adjacencyList.keys()) {
80      const neighbors = [];
81
82      neighbors.push(`${vertex}:`);
83
84      this.adjacencyList.get(vertex).forEach((neighbor) => {
85        neighbors.push(neighbor);
86      });
87
88      result.push(neighbors.join(' '));
89    }
90
91    return result;
92  }
93
94  verticesCount() {
95    return this.verticesCount;
96  }
97
98  reverse() {
99    const graph = new Graph();
100    for (let [src, dests] of this.adjacencyList) {
101      graph.addVertex(src);
102    }
103
104    for (let [src, dests] of this.adjacencyList) {
105      for (let dest of this.adjacencyList.get(src)) {
106        graph.adjacencyList.get(src).push(dest);
107      }
108    }
109
110    return graph;
111  }
112}
113
114var matrix1 = [
115  [1, 1, 0, 0, 0],
116  [0, 1, 1, 0, 0],
117  [0, 1, 0, 1, 0],
118  [1, 0, 0, 0, 0],
119];
120
121var matrix2 = [
122  [1, 1, 0, 0],
123  [0, 0, 1, 0],
124  [0, 1, 1, 0],
125  [1, 0, 0, 0],
126];
127
128var planeMatrix1 = [
129  ['.', '.', '.', 'P'],
130  ['.', '.', '.', 'P'],
131  ['P', 'P', '.', 'P'],
132  ['.', '.', '.', 'P'],
133];
134
135try {
136  assert.deepEqual(
137    floodFill(
138      [
139        [1, 1, 1, 1, 1, 1, 1],
140        [1, 1, 1, 1, 1, 1, 0],
141        [1, 0, 0, 1, 1, 0, 1],
142        [1, 2, 1, 2, 1, 2, 0],
143        [1, 2, 1, 2, 2, 2, 0],
144        [1, 2, 2, 2, 1, 2, 0],
145        [1, 1, 1, 1, 1, 2, 1],
146      ],
147      0,
148      0,
149      3
150    ),
151    [
152      [3, 3, 3, 3, 3, 3, 3],
153      [3, 3, 3, 3, 3, 3, 0],
154      [3, 0, 0, 3, 3, 0, 1],
155      [3, 2, 1, 2, 3, 2, 0],
156      [3, 2, 1, 2, 2, 2, 0],
157      [3, 2, 2, 2, 3, 2, 0],
158      [3, 3, 3, 3, 3, 2, 1],
159    ]
160  );
161
162  console.log(
163    'PASSED: `floodFill([   [1, 1, 1, 1, 1, 1, 1],   [1, 1, 1, 1, 1, 1, 0],   [1, 0, 0, 1, 1, 0, 1],   [1, 2, 1, 2, 1, 2, 0],   [1, 2, 1, 2, 2, 2, 0],   [1, 2, 2, 2, 1, 2, 0],   [1, 1, 1, 1, 1, 2, 1] ], 0, 0, 3)` should return `[[3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 0], [3, 0, 0, 3, 3, 0, 1], [3, 2, 1, 2, 3, 2, 0], [3, 2, 1, 2, 2, 2, 0], [3, 2, 2, 2, 3, 2, 0], [3, 3, 3, 3, 3, 2, 1] ]`;'
164  );
165} catch (err) {
166  console.log(err);
167}