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

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

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

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

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

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

• Просканируйте, пока не найдете 1

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

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

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

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

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

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);
                        }
                }
        }
}

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

Поиск:

0 1 0
0 1 1
0 1 0 

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

Сначала прогоните матрицу, добавив следующую матрицу ядра, центрируя 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

или что угодно.

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

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; 
}  

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

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

По крайней мере, менее 256. :)