Mikki0

Untitled

Jun 6th, 2021
680
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. func <- function(start_x, start_y, end_x, end_y, matrix){
  2.   n <- nrow(matrix) * ncol(matrix)
  3.   g <- graph.empty(n, directed = FALSE)
  4.   V(g)$name <- ''
  5.   V(g)[n - (start_x - 1) * ncol(matrix) - (ncol(matrix) - start_y)]$name <- 's'
  6.   V(g)[n - (end_x - 1) * ncol(matrix) - (ncol(matrix) - end_y)]$name <- 'e'
  7.   for (i in 1:nrow(matrix)) {
  8.     for (j in 1:ncol(matrix)) {
  9.       if (matrix[i, j] == -1) {
  10.         V(g)[n - (i - 1) * ncol(matrix) - (ncol(matrix) - j)]$color <- "red"
  11.       }
  12.     }
  13.   }
  14.   if (matrix[start_x, start_y] != -1) { # в стартовой вершине нет камня
  15.     dist <- matrix(Inf, nrow = nrow(matrix), ncol = ncol(matrix)) # массив расстояний от стартовой до всех остальных
  16.     used <- matrix(FALSE, nrow = nrow(matrix), ncol = ncol(matrix))
  17.     anc_x <- matrix(-1, nrow = nrow(matrix), ncol = ncol(matrix))
  18.     anc_y <- matrix(-1, nrow = nrow(matrix), ncol = ncol(matrix))
  19.     dist[start_x, start_y] <- 0
  20.     queue <- c(start_x, start_y)  # массив с вершинами, которые предстоит обработать  
  21.     i <- 1
  22.     while (i <= length(queue)) { # пока не дошла до конца массива
  23.       x <- queue[i]    # достаем коорлинаты очереденой вершины, которую нужно обработать
  24.       y <- queue[i + 1]
  25.       i <- i + 2
  26.       used[x, y] <- TRUE                                # пытаемся обновить расстояние до соседей
  27.       if (x + 1 > 0 && x + 1 <= nrow(matrix) && y > 0 && y <= ncol(matrix) && used[x + 1, y] == FALSE && matrix[x + 1, y] != -1) {
  28.         anc_x[x + 1, y] <- x                                                 # первые 4 условия отвечают за то, что мы не вышли за границы массивва
  29.         anc_y[x + 1, y] <- y
  30.         dist[x + 1, y] <- dist[x, y] + 1                                         # предпоследнее условие отвечает за то, что мы еще не побывали в этой вершине                                                   # последнее условие за то, что в вершину , в которую мы хотим пойти, нет камня
  31.         queue <- c(queue, x + 1, y)
  32.       }
  33.       if (x > 0 && x <= nrow(matrix) && y + 1 > 0 && y + 1 <= ncol(matrix) && used[x, y + 1] == FALSE && matrix[x, y + 1] != -1) {
  34.         anc_x[x, y + 1] <- x
  35.         anc_y[x, y + 1] <- y
  36.         dist[x, y + 1] <- dist[x, y] + 1
  37.         queue <- c(queue, x, y + 1)
  38.       }
  39.       if (x - 1 > 0 && x - 1 <= nrow(matrix) && y > 0 && y <= ncol(matrix) && used[x - 1, y] == FALSE && matrix[x - 1, y] != -1) {
  40.         anc_x[x - 1, y] <- x
  41.         anc_y[x - 1, y] <- y
  42.         dist[x - 1, y] <- dist[x, y] + 1
  43.         queue <- c(queue, x - 1, y)
  44.       }
  45.       if (x > 0 && x <= nrow(matrix) && y - 1 > 0 && y - 1 <= ncol(matrix) && used[x, y - 1] == FALSE && matrix[x, y - 1] != -1) {
  46.         anc_x[x, y - 1] <- x
  47.         anc_y[x, y - 1] <- y
  48.         dist[x, y - 1] <- dist[x, y] + 1
  49.         queue <- c(queue, x, y - 1)
  50.       }
  51.     }
  52.     if (dist[end_x, end_y] != Inf) {
  53.       cur_x <- end_x
  54.       cur_y <- end_y
  55.       while (anc_x[cur_x, cur_y] != -1 || anc_y[cur_x, cur_y] != -1) {
  56.         V(g)[n - (cur_x - 1) * ncol(matrix) -(ncol(matrix) - cur_y)]$color <- 'green'
  57.         temp_x <- anc_x[cur_x, cur_y]
  58.         temp_y <- anc_y[cur_x, cur_y]
  59.         cur_x <- temp_x
  60.         cur_y <- temp_y
  61.       }
  62.       V(g)[n - (start_x - 1) * ncol(matrix) - (ncol(matrix) - start_y)]$color <- 'green'
  63.     }
  64.     plot(g, layout = layout_on_grid)
  65.     return(dist[end_x, end_y])
  66.   } else {
  67.     return(Inf)
  68.   }
  69. }
  70.  
  71. library(igraph)
  72. func(3, 1, 1, 3, rbind(c(-1, 0, 0), c(0, 0, -1), c(0, -1, -1)))
RAW Paste Data