Определение значения на основе соседних ячеек в матрице

Question

Ввод: лабиринт, представленный матрицей произвольного размера. (Вне границ считается 0)

00100
00100
01110
11111
01110
00100

Вывод: красивое представление лабиринта (соседство отображается на wchar_t):

   ┌─┐
   │1│
  ┌┘1└┐
 ┌┘111└┐
 |11111|
 └┐111┌┘
  └┐1┌┘
   └─┘

Редактировать: В основном каждый 0 сопоставляется с 4-битным значением, представляющим разметку стены.

Мой подход и мысли:

Я думал, что было бы проще всего смотреть на каждую клетку за раз. Затем посмотрите на его соседей, чтобы определить, какую ценность там поставить. Оказывается, у меня есть 8 логических входов (все соседи), это генерирует 2 ^ 8 = 256 различных сценариев. Мне не хочется их все кодировать.

Есть ли более элегантный способ правильно отобразить значения?

Answer 1

Я реализовал это в моей победной записи для IOCCC 2004 года. Я уверен, что вы найдете код хорошо документированным и простым в использовании.

Если вы просто хотите получить ответ, насколько я помню, я выбрал подход, заключающийся в том, чтобы вычислить растровое изображение занятых ячеек, окружающих каждую ячейку, и использовать его в качестве индекса в массиве символов стены (или, что эквивалентно, глифов). Если, как и мое решение, вы не разрешаете перемещение по диагонали, растровое изображение имеет длину 4 бита, и, следовательно, массив имеет 2 ^ 4 = 16 элементов. Если вы разрешаете перемещение по диагонали, вам нужно 8-битное растровое изображение и 256 записей.

Answer 2

Сначала выполните матрицу, добавив следующую матрицу ядра, центрируя 0 ядра на каждом 1 и добавляя числа в соседние квадраты (то есть создайте двоичное представление всех соседей).

1   2   4 
8   16  32 
46  128 256  

Затем просто напишите список правил, одно правило для каждой фигуры , а не правило для каждой возможной суммы. Например,

s = s_ij  # the sum at the location of interest
if not s & 16:  # never write a symbol over a 1
    if s & 8 and not (s & 128 or s & 2): 
        c = "|"
    elif s ==128:
        c = “┌─┐”
    # etc

или что вы хотите.

Answer 3

Вдохновленный решением Дуга Т. Я сам написал следующее. В основном я бегу через матрицу дважды (низкая производительность: /). В первый раз, когда я буду рисовать стены вокруг каждого 1 в матрице, я делаю это с помощью битовых масок. Во второй раз я очищаю все "направленные внутрь" -стены.

Пример настройки:

// Add padding to output-matrix
int owidth = width+2;
int oheight = height+2;
// 4-bit value: 0bWSEN
static char N = 0x1; // The dash that goes from the center to the north
static char E = 0x2; // The dash that goes from the center to the east
static char S = 0x4; // ...
static char W = 0x8;
// This is what I will draw around every tile
char box[] = 
    {S|E, E|W, W|S,
     N|S,  0 , N|S,
     N|E, E|W, W|N };

Стенная петля:

for(unsigned int y = 0; y < height; y++)
    for(unsigned int x = 0; x < width; x++)
    {
        // We ignore walls
        if (! isOne(x, y)) // isOne takes care of out-of-bounds
            continue;
        // Go through neighbourhood
        for(int dy = -1; dy <= 1; dy++)
            for(int dx = -1; dx <= 1; dx++)
            {
                if (dy == 0 && dx == 0) // Ignore self
                    continue;

                if (! isOne(x+dx, y+dy))
                {
                    // Draw part of box
                    int ox = x+1, oy = y+1; // output-x and y
                    out[(oy+dy)*owidth+(ox+dx)] |= box[(dy+1)*3 + (dx+1)];
                }
            }
    }

Цикл очистки:

// Clean up "pointing edges"
for(unsigned int y = 0; y < height; y++)
    for(unsigned int x = 0; x < width; x++)
    {
        // We ignore zero's since we're only cleaning walls.
        if (isOne(x, y))
            continue;

        int ox = x+1, oy = y+1; // output-x and y
        // Remove edges that points to 'zero'-cells.
        if (! isOne(x  , y-1)) out[y*width+x] &= ~N;
        if (! isOne(x  , y+1)) out[y*width+x] &= ~S;
        if (! isOne(x-1, y  )) out[y*width+x] &= ~W;
        if (! isOne(x+1, y  )) out[y*width+x] &= ~E;
    }

Тогда у меня будет список поиска размером 16 (по одному на каждый символ) с одной записью для каждого символа.

map<unsigned int, wchar_t> p;
p[0] = ' ';
p[N] = '.';
// ...
p[N|S] = L'\u2502'; // │
p[E|W] = L'\u2500'; // ─
// ...
p[N|E|S|W] = L'\u253C'; // ┼

Этот алгоритм никоим образом не эффективен, O (2 * ширина * высота) не годится ... Его можно улучшить, сгенерировав таблицу циклов размера 256, как другие предлагали, это даст нам O 1) на исполнение.

Answer 4

Вместо того, чтобы сканировать каждую строку на 1 и рисовать каждую клетку, Вы могли бы "ходить" по стенам.

пока не в конце вашего массива bool:

• Сканирование, пока не найдете 1

определить функцию с именем "Draw", которая будет:

• Нарисуйте каждый соседний 0 (или за его пределами) в виде стены
• Измените текущее значение 1 на 3 (для этого потребуется использовать что-то отличное от массива bools)
• Переключение текущего курсора на соседний 1
  • Записаться в "Розыгрыш"
• Если таких соседей нет, вернитесь из Draw. стены.

- при возврате возобновить сканирование, пока не будет найден следующий 1 или конец ввода.

Возможно, не самый эффективный, но вы сказали элегантно. Рекурсия всегда элегантна! (пока вы не получите переполнение стека).

Вот некоторый взломанный код (не используйте магические числа, как я :)), чтобы помочь вам:

int inputIdxToOutputIdx(int idx)
{
        return (idx + 1);
}


int draw(int x, int y, int arr[6][6], char outBuff[8][8])
{
        for (int deltaX = -1; deltaX < 2; ++deltaX)
        {       
                for (int deltaY = -1; deltaY < 2; ++deltaY)
                {       
                        int currX = (x + deltaX);
                        int currY = (y + deltaY);
                        int drawX = inputIdxToOutputIdx(x) + deltaX; 
                        int drawY = inputIdxToOutputIdx(y) + deltaY; 
                        // if any adjacent to 1 are 0 or off the map,
                        // draw a border
                        arr[x][y] = 3;
                        if (currX > 5 || currY > 5 || currX < 0 || currY < 0 || arr[currX][currY] == 0)
                        {       
                                printf("Drawing at %i, %i (%i,%i)\n", currX, currY,drawX,drawY);
                                outBuff[drawX][drawY] = '*';
                        }       
                        else if (arr[x][y] == 1) 
                        {       
                                draw(currX, currY, arr, outBuff);
                        }       
                }
        }
}


// make the output buffer size of input + 2
int printMaze(int arr[6][6], char outBuff[8][8])
{
        for (int x = 0; x < 6; ++x)
        {
                for (int y = 0; y < 6; ++y)
                {
                        // this might be able to be made more efficient.
                        if (arr[x][y] == 1)
                        {
                                draw(x, y, arr, outBuff);
                        }
                }
        }
}

В приведенном выше решении я просто рисую '*' '. Однако, если бы вы хотели нарисовать конкретную фигуру для данной ситуации, я бы использовал таблицу поиска, такую ​​как walkytalky в своем комментарии. Сопоставьте заданный набор смежных 1 и 0 с заданным фрагментом. IE:

Глядя вверх:

0 1 0
0 1 1
0 1 0 

даст результат "Т" для центральной части стены. Обязательно относитесь к «вне карты» как к эквивилланту до 0.

Когда все сказано и сделано, простое сканирование с таблицей подстановки, основанной на смежных фрагментах (без рекурсии), может быть вашим лучшим выбором, если вы не сможете сделать вышеупомянутое решение более умным, чтобы не пересматривать то, что уже отсканировано.

Answer 5

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

Answer 6

Просто быстрый взлом. Используя массив 3х3 и некоторую арифметику по модулю, вы, вероятно, сможете значительно уменьшить количество обращений к памяти, но это может выглядеть уродливо. Предупреждение Я не запускал его через компилятор, поэтому он может содержать опечатки.

wchar_t maze_wall(int** input,int rows, int cols){

   wchar_t** output;
   int i,j;
   int N,E,S,W,NE,SE,NW,SW;

   output = (wchar_t**) malloc(sizeof(wchar_t*)*rows);
   for(i=0;i<cols;i++)
      output[i]= (wchar_t*) malloc(sizeof(wchar_t)*cols);
   for(i=0;i<rows;i++){
      for(j=0;j<cols;j++){
        if(input[i][j] ==1)
           {output[i][j] = '1'; continue;}
        N=E=S=W=NE=SE=NW=SW=0;
        if(i != 0) /*We are not at the top*/
           N = input[i-1][j];
        if(i != rows-1) /* We are not at the bottom*/
          S = input[i+1][j];
        if(j != rows-1) /* We are not at the right side*/
          E = input[i][j+1];
        if(j != 0) /* We are not at the left side*/
          W = input[i][j-1];
      /*Expand this for the corners*/

      if(N+E+S+W+NE+SE+SW+NE+NW == 0)
          {output[i][j] = ' '; continue;}

      /*Fill it in for the other six cases {'└', '┐', '┌', '┘', '-', '|'} */
      } 
   }
   return output; 
}  

Answer 7

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

Это должно немного сузить, я надеюсь. :) вертикальный, горизонтальный и четыре разных края. Это 6 случаев, как только вы обнаружили, какие из них вообще являются ребрами.

Менее 256 минимум. :)