3 Раскраска двумерного массива с javascript - PullRequest
Новая
       6

3 Раскраска двумерного массива с javascript

2 голосов
/ 17 апреля 2020

Я пытаюсь нарисовать фигуры с 5 ячейками в трех цветах.

5 x 5 rectangular

Теперь они просто окрашены в разные цвета. Но я пытаюсь покрасить их только в три цвета, такие как красный, синий, желтый. Я думаю, что это похоже на теорему о четырех цветах, но у меня есть проблема с ее реализацией. 

let board = [
  [1,1,2,2,2],
  [1,3,3,2,2],
  [1,3,3,4,4],
  [1,3,4,4,4],
  [5,5,5,5,5]
] // set board

let w = 30 // width

function setup() {
  createCanvas(500, 500);

  // loop through every element in array a
  for (let i = 0; i < 5; i++) {

    // loop through every element in array a[i]
    for (let j = 0; j < 5; j++) {
      fill("white")
      rect(i * w, w * j, w, w);
    }
  }

}

function draw(){

  for(let i =0; i< 5; i++){
      for(let j =0; j< 5; j++){
        if(board[i][j] == 1){
          fill("red")
          rect(i * w, w * j, w, w);
        }

        if(board[i][j] == 2){
          fill("blue")
          rect(i * w, w * j, w, w);
        }

        if(board[i][j] == 3){
          fill("yellow")
          rect(i * w, w * j, w, w);
        }

        if(board[i][j] == 4){
          fill("green")
          rect(i * w, w * j, w, w);
        }

        if(board[i][j] == 5){
          fill("orange")
          rect(i * w, w * j, w, w);
        }
    }
  } 
}

Я тестировал размер 15 x 15 и пытался сравнить строки одну за другой, но я не думаю, что это правильно. Сейчас я тестирую его в маленьком прямоугольнике, как мне это реализовать? Любая помощь будет оценена.

1 Ответ

1 голос
/ 17 апреля 2020

Просто для пояснения, в итоге, теорема о четырех цветах гласит, что для раскраски 2D-карт достаточно четырех цветов с некоторыми дополнительными ограничениями на то, что считается границей. Он не соответствует алгоритму определения раскраски.

Теперь раскраска работает в областях, граничащих друг с другом, а не в отдельных ячейках. Однако клетки необходимы, чтобы выяснить эти границы. Поэтому первым шагом является вычисление матрицы смежности по ячейкам на доске. Это так же просто, как проверка, к какой области принадлежит каждый из четырех соседей каждой ячейки. Существует необходимый средний шаг, чтобы проверить, находится ли текущая ячейка сбоку или в углу доски. 

let SIZE = 5
let regions = {}
for (let i = 0; i < SIZE; i++) {
    for (let j = 0; j < SIZE; j++) {
        region = board[i][j]
        if (region not in regions) {regions[region] = {}}
        if (i > 0) {
            if (board[i-1][j] != region) {
                regions[region][board[i-1][j]] = true
            }
        }
        if (i < SIZE - 1) {
            if (board[i+1][j] != region) {
                regions[region][board[i+1][j]] = true
            }
        }
        if (j > 0) {
            if (board[i][j-1] != region) {
                regions[region][board[i][j-1]] = true
            }
        }
        if (j < SIZE - 1) {
            if (board[i][j+1] != region) {
                regions[region][board[i][j+1]] = true
            }
        }
    }
}

Теперь regions говорит вам, какие соседи имеют каждый регион. Одним из способов получить раскраску является рассмотрение этой проблемы удовлетворенности ограничениями и ее решение путем отслеживания возможных значений для каждого региона, определения цвета для региона, выполнения распространения ограничений, проверки несоответствий и возврат в случае нарушения ограничений.

Полный алгоритм и его реализация выходят за рамки этого вопроса. Но выяснение связей между регионами является необходимым шагом в любом случае. Вы также можете попытаться решить CSP, просто попробовав все комбинации, хотя я не ожидаю, что это будет очень хорошо масштабироваться.

...