Finding shortest path in two dimensional array (Ja

问题:

I am trying to implement an algorithm, that finds the shortest path in the following two dimensional array (from the top left corner, to the right bottom corner):

      [ [ 'A', 'A', 'A', 'B', 'A' ],
        [ 'B', 'B', 'B', 'B', 'B' ],
        [ 'A', 'B', 'A', 'A', 'A' ],
        [ 'A', 'B', 'B', 'B', 'B' ],
        [ 'A', 'A', 'A', 'A', 'A' ] ]

The rules are, that the path must alternate between A's and B's.

The output must be a number specifying the smallest number of steps it will take to go through the array. (In the example the expected output is 13)

Does anyone know of a simple Graph implementation that can help me solve this problem?

回答1:

Since it represents an undirected unweighted graph, you can simply use BFS:

const m =
  [ [ 'A', 'A', 'A', 'B', 'A' ],
    [ 'B', 'B', 'B', 'B', 'B' ],
    [ 'A', 'B', 'A', 'A', 'A' ],
    [ 'A', 'B', 'B', 'B', 'B' ],
    [ 'A', 'A', 'A', 'A', 'A' ] ]

let successors = (root, m) => {
  let connectedCells = [
    [root[0] - 1, root[1]],
    [root[0], root[1] - 1],
    [root[0] + 1, root[1]],
    [root[0], root[1] + 1]
  ]

  const validCells = connectedCells.filter(
    (cell) => (
      cell[0] >= 0 && cell[0] < m.length 
      && cell[1] >= 0 && cell[1] < m[0].length)
  )

  const successors = validCells.filter(
    (cell) => (m[cell[0]][cell[1]] !== m[root[0]][root[1]])
  )

  return successors
}

const buildPath = (traversalTree, to) => {
  let path = [to]
  let parent = traversalTree[to]
  while (parent) {
    path.push(parent)
    parent = traversalTree[parent]
  }
  return path.reverse()
}

const bfs = (from, to) => {
  let traversalTree = []
  let visited = new Set
  let queue = []
  queue.push(from)

  while (queue.length) {
    let subtreeRoot = queue.shift()
    visited.add(subtreeRoot.toString())

    if (subtreeRoot.toString() == to.toString()) return buildPath(traversalTree, to)

    for (child of successors(subtreeRoot, m)) {
      if (!visited.has(child.toString())){
        traversalTree[child] = subtreeRoot
        queue.push(child)
      }
    }
  }
}


console.log(bfs([0,0], [4,4]).length) // => 13

回答2:

Well you can use grids as graphs without converting them to usual graph adjacency list representation.

So every pair (row,column) is a node,

You can go to next node only if: 2 nodes are neighbors and have different values,

The purpose of adjacency list is to get neighboring nodes efficient, but with grid cells you can just always check all 4 directions and process nodes that exist.

Sample code:

let A = [ [ 'A', 'A', 'A', 'B', 'A' ],
        [ 'B', 'B', 'B', 'B', 'B' ],
        [ 'A', 'B', 'A', 'A', 'A' ],
        [ 'A', 'B', 'B', 'B', 'B' ],
        [ 'A', 'A', 'A', 'A', 'A' ] ];
		
let visited = new Set();
let rows = A.length;
let columns = A[0].length;
let distance = Array(rows).fill().map(() => Array(columns).fill(-1));
distance[0][0]=0;
let Q = []; //Queue
Q.push([0,0]);
visited.add([0,0].toString());

let dr = [-1,1,0,0]; 
let dc = [0,0,-1,1]; 

while(Q.length > 0)
{
	let cur = Q.shift();
	let row = cur[0];
	let col = cur[1];
	
	for(let k=0; k<4; k++)
	{
		let newRow = row + dr[k];
		let newCol = col + dc[k];
		
		if(!visited.has([newRow,newCol].toString()) && newRow>=0 && newCol >=0 && newRow < rows && newCol < columns && A[newRow][newCol] !== A[row][col])
		{
			visited.add([newRow,newCol].toString());
			distance[newRow][newCol] = distance[row][col] + 1;
			Q.push([newRow,newCol]);
		}
	}
}

if(distance[rows-1][columns-1] === -1)console.log("Path does not exist");
else console.log(distance[rows-1][columns-1]);

回答3:

One way to solve your problem is to first represent your 2D array as a graph, where each letter is a node, and there exists an edge between two nodes if the letter they represent are neighbor in the array, and these letters are different (one A and one B).
Then all you have to do is to use a classical shortest path algorithm, such as Dijkstra's, or A*, to find the shortest path between two nodes of your graph. This will be equivalent to finding the shortest path between two letters of your array.

Edit: here is a pseudocode to answer the question you asked in the comment.

nodes = init_a_2d_array_of_graph_nodes(ARRAY_WIDTH, ARRAY_HEIGHT)
for i from 1 to ARRAY_WIDTH:
    for j from 1 to ARRAY_HEIGHT:
        if i < ARRAY_WIDTH and array[i][j] != array[i+1][j]:
            add_edge(nodes[i][j], nodes[i+1][j])
        if j < ARRAY_HEIGHT and array[i][j] != array[i][j+1]:
            add_edge(nodes[i][j], nodes[i][j+1])

First, you need to initialize a graph structure. If you don't know how to do that, check online, there must be plenty of ways to do it, it is rather simple.

Then, you need to create one node for each letter in your array. It is convenient to store these node in a 2D array as well, so you can find out easily which letter of your array corresponds to which node in your graph. Then, for all neighbor letters, you check if these letters are different (that is what is checked in the 2 if conditions). If it is the case, you connect the two nodes with an edge.

After that, you'll need to run a shortest path algorithm on your graph, between your source node and destination node. Dijkstra's algorithm is the best way to get started with shortest path algorithm, it is the most widely used, and is fast enough in most of the situations you'll encounter.

Finally, once you have your path, you need to retrieve the index (row and column) of the nodes of your graph, that will give you the corresponding path in your letters array.

Feel free to comment again if there is still something you do not understand.

回答4:

Does anyone know of a simple Graph implementation that can help me solve this problem?

The Dijkstra algortihm is used to find the shortest path between two nodes. Every position in your two-dimensional array represents a node, the edges are dynamically derived from the surrounding nodes that fulfill your "alternating" rule.

You can further optimise it for your use case with bidirectional search and a goal metric (A*).