如何在二维数组中找到最大的圆

Question

给定一个二维n*n数组，每个元素都是+或x，我们如何找到仅由+个字符组成的最大圆直径

例如:

xxxxx  
x++++
x+++x
x+++x
xxxxx

的最大直径为2，圆心为圆心。

在任何情况下，圆形都不能在2D数组中居中。

是否有一个简单的算法来解决这个问题?我不是在找代码，只是一个算法。谢谢。

xxxxx
xx+xx
x+++x
xx+xx
xxxxx

将是一个直径为2的圆来回答关于边的问题

Answer 1

解决这个问题的一种方法是，将自由单元格(+)想象为海洋，而将其他单元格(x)想象为陆地。该算法在海岸线上启动一个向各个方向流动的水波(直到它碰到另一个波浪或陆地)。最后被海浪覆盖的一片海域是半径最大的圆的中心。

这导致了更正式的算法:

1. 设count为空闲细胞数(+的个数)。
2. 如果count为零，退出无结果
3. 创建一个数组coast，其中包含已占用单元格的单元格坐标(x)
   • 还向coast添加位于网格外的虚拟单元格，因为它们也代表"土地"。
4. 设置radius为1

5. 获取这个radius的圆的相对坐标(好像以单元格[0,0]为中心)。所以对于半径1，这是

   [ [-1, 0], [0, -1], [1, 0], [0, 1] ]
   

6. 对于coast中引用的每个centre = cell:

   • 获取圆圈上centre和radius的空闲单元格，分别为:
     • 标记为已占用，减小count
     • 如果count为零，那么我们有一个解决方案:这个单元格是要绘制的圆的中心，它的半径应该是radius-1。退出。
   • 如果此圈中没有空闲单元格，则从coast中删除centre(以避免将来不必要的检查)

,7. 增加radius并从步骤5重复。

当算法退出并得到结果(中心和半径)时，可以直接将给定网格与实际磁盘覆盖。

下面是一个JavaScript实现(没有使用任何新的语法，所以应该很容易阅读)，你可以在这里运行:

"use strict";
function circleCoordinates(radius) {
    var cells = [];
    var r2 = (radius+0.41)*(radius+0.41); // constant determines margin
    var i = 0;
    var j = radius;
    while (i <= j) {
        cells.push([ i,  j]);
        cells.push([ i, -j]);
        if (i < j) {
            cells.push([ j,  i]);
            cells.push([-j,  i]);
        }
        if (i) {
            cells.push([-i,  j]);
            cells.push([-i, -j]);
            if (i < j) {
                cells.push([j,  -i]);
                cells.push([-j, -i]);
            }
        }
        i++;
        if (i*i + j*j > r2) {
            j--; 
            // Decrementing i here is not standard, but needed to make 
            // sure we cover the surface added compared to a disk with 
            // a radius of one unit one less.            
            i--;
        }
    }
    return cells;
}
function solve(a) {
    var i, j, k, l, m, n, count, coast, circle, reduced, radius, b;
    function get(b, i, j) {
        if (i < 0 || j < 0 || i >= b.length || j >= b[i].length)
            return 1;
        return b[i][j];
    }
    // Copy input, count free cells, and collect the others in "coast"
    count = 0;
    coast = [];
    b = [];
    for (i = 0; i < a.length; i++) {
        b[i] = [];
        for (j = 0; j < a[i].length; j++) {
            b[i].push(a[i][j]); // copy array element
            count += !b[i][j]; // count free cells
            if (b[i][j]) coast.push([i,j]); // push occupied cells
        }
    }
    if (!count) return; // no solution
    // To bound the area, add virtual border cells in 'coast':
    for (i = 0; i < b.length; i++) {
        coast.push([i, -1], [i, b[i].length]);
    }
    for (j = 0; j < b[0].length; j++) {
        coast.push([-1, j], [b.length, j]);
    }
    // Keep reducing free space by drawing circles from the coast
    // until one free cell is left over.
    radius = 0;
    while (count) {
        radius++;
        circle = circleCoordinates(radius);
        for (k = coast.length - 1; (k >= 0) && count; k--) {
            reduced = false;
            for (l = 0; (l < circle.length) && count; l++) {
                m = coast[k][0] + circle[l][0];
                n = coast[k][1] + circle[l][1];
                if (!get(b, m, n)) {
                    b[m][n] = radius+1;
                    count--;
                    reduced = true;
                }
            }
            // Save some time by removing the cell in the coast
            // list that had no reducing effect anymore:
            if (!reduced) coast.splice(k, 1);
        }
    }
    // Greatest circle has a radius that is one smaller:
    radius--;
    // Restore array to original
    for (i = 0; i < b.length; i++) {
        for (j = 0; j < b[i].length; j++) {
            b[i][j] = a[i][j];
        }
    }
    // Draw a disc centered at i, j
    circle = circleCoordinates(radius);
    for (l = 0; l < circle.length; l++) {
        for (k = m + circle[l][0]; k <= m - circle[l][0]; k++) {
            b[k][n+circle[l][1]] = 2;
        }
    }
    // Return the array with the marked disc
    return b;
}
// String handling
function cleanText(txt) {
    return txt.trim().replace(/[ rt]/g, '').replace(/[^xn]/g, '+');
}
function textToArray(txt) {
    var lines, a, i, j;
    // Clean text and split into lines
    lines = cleanText(txt).split('n');
    // convert to 2D array of 0 or 1:
    a = [];
    for (i = 0; i < lines.length; i++) {
        a[i] = [];
        for (j = 0; j < lines[i].length; j++) {
            a[i][j] = +(lines[i][j] !== '+'); // '+' => 0, 'x' => 1
        }
    }
    return a;
}
function arrayToText(a) {
    // Convert 2D array back to text. 2-values will be translated to '#'
    var lines, i, j;
    lines = [];
    for (i = 0; i < a.length; i++) {
        lines[i] = [];
        for (j = 0; j < a[i].length; j++) {
            lines[i][j] = '+x#'[a[i][j]]; // mark disc with '#'
        }
        lines[i] = lines[i].join('');
    }
    return lines.join('n');
}
// I/O handling for snippet:
var inp = document.querySelector('textarea');
var solveBtn = document.querySelector('#solve');
var clearBtn = document.querySelector('#clear');
solveBtn.onclick = function() {
    // Convert input to 2D array of 0 and 1 values:
    var a = textToArray(inp.value);
    // Draw greatest disk by replacing 0-values with 2-values:
    a = solve(a);
    // Convert 2D array back to text. 2-values will be translated to '#'
    inp.value = arrayToText(a);
};
clearBtn.onclick = function() {
    inp.value = cleanText(inp.value);
};

<button id="solve">Show Greatest Disc</button>
<button id="clear">Remove Disc</button><br>
<textarea rows=10>
xxxxxxxxxxxxxxxxxx
xxxxx++++++x++++++
+++x+++++++x+++++x
++++x+++++++++++x+
++++x+++++x++++x++
+++x+++++++x+++x+x
x+++++xx+++++x++++
xx+++++x+++++x+++x
++++++xxxx++xxxx++
xxx++xxxxxxxxxxxx+
++xxxxxxxxx+xxxxxx</textarea>
<pre></pre>