基于矩阵中的相邻单元的确定值

Question

输入：由任意大小的矩阵表示的迷宫。 （出界计为0）

00100 
00100 
01110 
11111 
01110 
00100 

输出：迷宫（附近被映射到一个wchar_t）一个好看表示：

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

编辑：基本上各自为0得到映射到表示墙布局的4位值。

我的做法和想法：

我认为这将是最简单的看一下每个单元在同一时间。然后看看它的邻居，以确定放在那里的价值。原来我有8个布尔输入（所有邻居），这会产生2^8 = 256个不同的场景。我不想把它们全部编码。

有更好的方法来正确映射值吗？

Answer 1

通过Doug T.的解决方案的启发我写了下面自己。 基本上我跑过矩阵两次（糟糕的表现：/）。我第一次在矩阵中的每个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 2

你可以通过在别人之前查看一些单元格来甄别它，但是，老实说，256并不是那么多。编写一个程序来生成它们或者手动执行它并使用一个查找表，额外的256个字节（你可以将查找映射到另一个索引来获得实际的字符）足够小以至于不用担心。

Answer 3

如果您第一次发现哪些瓷砖是墙壁，那么为每种墙壁类型编码一个特殊情况，例如，如果左侧和/或右侧有一个，但是没有顶部或底部，则为垂直。

这应该缩小一点，我希望。 :)垂直，水平和四个不同的边缘。一旦你发现哪些边缘是边缘的，那就是6种情况。

至少少于256。 :)

Answer 4

而不是扫描每行1和绘制每个单元格，你可以“走”的墙壁。

，而不是在你的布尔数组的结束：

• 扫描，直到找到一个1

定义了一个名为 “画”，这将功能：

• 绘制每个相邻0（或越界）作为墙
• 将当前1更改为3（这将需要您使用除数组之外的其他值的bool）
• 交换机当前光标到相邻的1
  • 递归处理“画”
• 如果没有这样的相邻的存在，从绘制的回报。的墙壁。

-upon返回，恢复扫描，直到找到下一个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); 
         } 
       } 
     } 
} 

在上述方案，我只是画“*”的。然而，如果你想绘制一个特定的情况下，我会使用查找表，如walkytalky在他的评论中说。将给定的一组相邻的1和0映射到一个给定片段。 IE：

仰视：

0 1 0 
0 1 1 
0 1 0 

将给出中心壁件为 “T” 的结果。一定要把“关闭地图”视为equivelant为0.

当所有的说法和完成只是一个查找表基于相邻件（没有递归）的直接扫描可能是你最好的选择，除非你可以使上述解决方案更智能地关于不重新扫描已经扫描的内容。

Answer 5

只是一个快速入侵。使用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; 
} 

Answer 6

我在2004年IOCCC的my winning entry中实现了这个功能。我相信你会发现代码有很好的记录和易于遵循。

如果你只是想回答，我记得，我采取的方法是计算围绕每个单元格占用的单元格的位图，并将其用作墙壁字符数组（或等效的字形）的索引。如果像我的解决方案一样，您不允许对角线传输，则位图长度为4位，因此阵列中有2^4 = 16个元素。如果您确实允许对角线旅行，您需要一个8位位图和256个条目。

Answer 7

首先运行矩阵，添加以下核矩阵，将内核的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 

或任何你想要的。