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

Question

输入:由任意大小的bool矩阵表示的迷宫.(超出范围计为0)

00100
00100
01110
11111
01110
00100

输出:迷宫的漂亮表示(邻域被映射到a wchar_t):

   ???
   ?1?
  ??1??
 ??111??
 |11111|
 ??111??
  ??1??
   ???

编辑:基本上每个0都被映射到表示墙布局的4位值.

我的方法和想法:

我认为一次看每个细胞最简单.然后看看它的邻居来确定放在那里的价值.结果我有8个布尔输入(所有邻居),这产生2 ^ 8 = 256个不同的场景.我不觉得他们都很难编码.

是否有更优雅的方法来正确映射值？

Answer 1

受到Doug T.的解决方案的启发，我自己编写了以下内容。\n基本上我运行了矩阵两次（性能不佳：/）。第一次我将1在矩阵中的每个周围绘制墙壁，我使用位掩码来完成此操作。第二次我清理了所有“向内”的墙壁。

\n\n

设置示例：

\n\n

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

\n\n

墙环：

\n\n

for(unsigned int y = 0; y < height; y++)\n    for(unsigned int x = 0; x < width; x++)\n    {\n        // We ignore walls\n        if (! isOne(x, y)) // isOne takes care of out-of-bounds\n            continue;\n        // Go through neighbourhood\n        for(int dy = -1; dy <= 1; dy++)\n            for(int dx = -1; dx <= 1; dx++)\n            {\n                if (dy == 0 && dx == 0) // Ignore self\n                    continue;\n\n                if (! isOne(x+dx, y+dy))\n                {\n                    // Draw part of box\n                    int ox = x+1, oy = y+1; // output-x and y\n                    out[(oy+dy)*owidth+(ox+dx)] |= box[(dy+1)*3 + (dx+1)];\n                }\n            }\n    }\n

\n\n

清理循环：

\n\n

// Clean up "pointing edges"\nfor(unsigned int y = 0; y < height; y++)\n    for(unsigned int x = 0; x < width; x++)\n    {\n        // We ignore zero\'s since we\'re only cleaning walls.\n        if (isOne(x, y))\n            continue;\n\n        int ox = x+1, oy = y+1; // output-x and y\n        // Remove edges that points to \'zero\'-cells.\n        if (! isOne(x  , y-1)) out[y*width+x] &= ~N;\n        if (! isOne(x  , y+1)) out[y*width+x] &= ~S;\n        if (! isOne(x-1, y  )) out[y*width+x] &= ~W;\n        if (! isOne(x+1, y  )) out[y*width+x] &= ~E;\n    }\n

\n\n

然后，我将得到一个 16 大小（每个符号一个）的查找列表，每个字符一个条目。

\n\n

map<unsigned int, wchar_t> p;\np[0] = \' \';\np[N] = \'.\';\n// ...\np[N|S] = L\'\\u2502\'; // \xe2\x94\x82\np[E|W] = L\'\\u2500\'; // \xe2\x94\x80\n// ...\np[N|E|S|W] = L\'\\u253C\'; // \xe2\x94\xbc\n

\n\n

这个算法无论如何都不是高效的，O(2*width*height) 不好......它可以通过生成一个 256 大小的循环表来改进，正如其他人建议的那样，这会给我们 O(1)关于执行。

\n