A Game on the Chessboard

Question

Description

On the chessboard of size 4x4 there are 8 white and 8 black stones, i.e. one stone on each field. Such a configuration of stones is called a game position. Two stones are adjacent if they are on fields with a common side (i.e. they are adjacent in either horizontal or vertical direction but not diagonal). It means that each stone has at most 4 neighbours. The only legal move in our game is exchanging any two adjacent stones. Your task is to find the shortest sequence of moves transforming a given starting game position into a given final game position.
Input

The starting game position is described in the first 4 lines of input. There are 4 symbols in each line, which define the colour of each stone in the row from the left to the right. The lines describe the rows of the chessboard from the top to the bottom. Symbol 0' means a white stone and symbol1' a black one. There is no space symbol separating the symbols in the line. The fifth line is empty. The next 4 following lines describe the final game position in the same way.
Output

The first line of output contains the number of the moves. The following lines describe the sequence of moves during the game. One line describes one move and it contains 4 positive integers R_1 C_1 R_2 C_2 separated by single spaces. These are the coordinates of the adjacent fields for the move, i.e. fields [R_1,C_1] and [R_2,C_2], where R_1 (or R_2) is the number of the row and C_1 (or C_2) is the number of the column. The rows on the chessboard are numbered from 1 (top row) to 4 (bottom row) and the columns are numbered from 1 (the leftmost column) to 4 (the rightmost one) as well (i.e. the coordinates of the left upper field are [1,1]). If there are multiple shortest sequences of moves transforming the starting position to the final position, you can output any one of them.
Sample Input

1111
0000
1110
0010

1010
0101
1010
0101
Sample Output

4
1 2 2 2
1 4 2 4
3 2 4 2
4 3 4 4

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

# read data
strokes <- readLines("input.txt")
moves <- strokes[5:6]

# get initial and final positions
start <- matrix(strokes[1:4], nrow = 4)
end <- matrix(strokes[7], nrow = 4)

# get adjacency list
adjacency <- buildAdjacencyList(start)

# calculate all possible paths
paths <- pathFinding(adjacency, start, end)

# sort paths by length
sortedPaths <- sort(paths, decreasing = TRUE)

# print sorted paths
for (i in seq_along(sortedPaths)) {
  print(paste("Path", i + 1, ":", sortedPaths[[i]]))
}

# function to convert adjacency matrix to adjacency list
buildAdjacencyList <- function(stones) {
  adj <- matrix(NA, nrow = 4 * 4, ncol = 4 * 4)
  
  # fill adjacency matrix
  for (i in 1:4) {
    for (j in 1:4) {
      if (stones[i, j] == '0') {
        adj[i, j] <- adj[j, i]
      } else {
        adj[i, j] <- adj[j, i] + 1
      }
    }
  }
  
  return(adj)
}

# function to perform Dijkstra's algorithm
pathFinding <- function(matrix, start, end) {
  adj <- matrix
  
  # create an empty queue for BFS
  queue <- list()
  
  # add source node to the queue
  queue[[1]] <- c(start[1], start[2])
  
  while (!queue[[length(queue)]]) {
    # remove the first element from the queue
    curr <- queue[[1]]
    
    # delete the current node from the adjacency matrix
    adj[curr[1], curr[2]] <- NA
    
    # update the distance values of adjacent nodes
    for (i in 1:nrow(adj)) {
      for (j in 1:nrow(adj)) {
        if (adj[i, j] != NA && adj[i, j] < adj[curr[1], curr[2]]) {
          adj[i, j] <- adj[i, j] + 1
          queue[[i]] <- queue[[i]] - c(curr[1], curr[2])
        }
      }
    }
    
    # add the updated node to the queue
    queue[[queue[[1]][[1]]]] <- c(queue[[1]][[2]], queue[[1]][[3]])
  }
  
  # return the shortest path
  return(queue[[1]])
}