javascript - 给定一个数据矩阵，计算 html rowspan 和 colspan

Question

我有一个如下所示的稀疏矩阵，由数据单元格 (1..9) 和空单元格 (=0) 组成:

[
    [ 1, 2, 0, 3 ],
    [ 0, 4, 0, 0 ],
    [ 5, 6, 7, 8 ],
]

我想将其显示为 html 表格，但不应有空单元格 - 它们应该被相邻数据单元格的行和列跨度“覆盖”:

<table border=1 cellpadding=10>
    <tr>
        <td rowspan=2>1</td>
        <td colspan=2>2</td>
        <td>3</td>
    </tr>
    <tr>
        <td colspan=3>4</td>
    </tr>
    <tr>
        <td>5</td>
        <td>6</td>
        <td>7</td>
        <td>8</td>
    </tr>
</table>

(这是一种可能的实现方式，我们也可以在第二行使用 colspan=4 而没有 rowspan)。

生成实际的 html 不是问题，但我无法编写算法来计算数据单元格的行和列跨度。

编辑:仍在为此寻找答案。仅使用 colspans 并将每个数据单元与其左侧/右侧的空单元连接起来似乎很简单。但是，我希望单元格尽可能呈方形，因此答案也应包括行跨度逻辑。谢谢!

EDIT2:到目前为止所有的答案都总结在这里:http://jsfiddle.net/ThQt4/

Answer 1

您需要考虑一些事项。

如果您总是喜欢正方形而不是最大的形状，您最终可能会得到很多单行和单列，因为矩形总是以正方形开头。并且正方形或矩形只有在左上角有值时才能开始。

考虑这个数组:

[1, 2, 3, 4, 5],
[7, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[1, 2, 0, 0, 5]

如果您选择正方形而不是最大的形状，您最终会得到一个正方形和三列

[1] [2] [3] [4] [5] instead of [1] [2] [3] [4] [5]
[  7  ] [ ] [ ] [ ]            [        7        ]
[     ] [ ] [ ] [ ]            [                 ]

此外，您最终可能会得到空的单个单元格:

[1, 1, 2, 0],   gives   [1] [1] [  2  ]
[3, 0, 0, 0],           [         ] [?] <---
[0, 0, 0, 5],           [    3    ] [5]
[0, 0, 0, 1]            [         ] [1]

此处最大的正方形大小为 3x3，从 3 开始。如果您先声明 3x3，然后声明从 2 开始的行，您将以 [?] 大于 5 的空单元格结束。

最后一件事，如果你在顶行或左列中有零，你也可能会遇到麻烦:

                                             V
[1, 0, 0, 2],  will leave you with  [  1  ] [?] [2]
[0, 0, 3, 4],                       [     ] [3] [4]
[0, 5, 6, 7]                    --->[?] [5] [6] [7]

也就是说，也许您的数组没有那么复杂，也许您不介意空单元格。无论哪种方式，用您的规范解决这个难题都很有趣。我的解决方案遵循以下规则:

1) 方 block 先行。

2) 大小很重要。越大越好

3) 行和列:大小很重要。最大的先。

4) Colspan 遍历 rowspan

Fiddle

var maxv = arr.length;
var maxh = arr[0].length;
var rsv = [];
var rsh = [];
pop_arr();
var shape;
try_sq();
try_rect();
try_loose();


//TRY SQUARES FIRST
function try_sq() {
    var sv, sh;
    shape = [];
    for (sv = 0; sv < maxv - 1; sv++) {
        for (sh = 0; sh < maxh - 1; sh++) {
            if (arr[sv][sh] === 0 || rsv[sv][sh] > -1 || rsh[sv][sh] > -1) {
                continue;
            }
            check_sq(sv, sh);
        }
    }
    if (shape.length > 0) {
        occu();
    }
}


//TRY RECTANGLES
function try_rect() {
    var sv, sh;
    var rect = false;
    do {
        shape = [];
        for (sv = 0; sv < maxv; sv++) {
            for (sh = 0; sh < maxh; sh++) {
                if (arr[sv][sh] === 0 || rsv[sv][sh] > -1 || rsh[sv][sh] > -1) continue;
                check_rec(sv, sh);
            }
        }
        if (shape.length > 0) {
            occu();
        } else {
            rect = false;
        }
    } while (rect === true);
}

//TRY LOOSE
function try_loose() {
    var sv, sh;
    //SET THE 1x1 with value
    for (sv = 0; sv < maxv; sv++) {
        for (sh = 0; sh < maxh; sh++) {
            if (arr[sv][sh] !== 0 && (rsv[sv][sh] == -1 || rsh[sv][sh] == -1)) {
                rsv[sv][sh] = 1;
                rsh[sv][sh] = 1;
            }
        }
    }
    //SEARCH FOR rectangles wit no value
    var rect = true;
    do {
        shape = [];
        for (sv = 0; sv < maxv; sv++) {
            for (sh = 0; sh < maxh; sh++) {
                if (arr[sv][sh] !== 0 || (rsv[sv][sh] > -1 || rsh[sv][sh] > -1)) {
                    continue;
                }
                rect = check_loose(sv, sh);
            }
        }
        if (shape.length > 0) occu();
        else {
            rect = false;
        }
    } while (rect === true);
}


//check SINGLES 
function check_loose(start_v, start_h) {
    var vd, hd, iv, ih, rect;
    var hor = ver = 1;
    var horb = 0;
    var mxv = maxv - 1;
    var mxh = maxh - 1;
    rect = true;
    vd = start_v + ver;
    hd = start_h + hor;

    //check horizontal
    for (sh = start_h + 1; sh <= mxh; sh++) {
        if (arr[start_v][sh] !== 0 || rsh[start_v][sh] > -1) {
            break;
        }
        hor++;
    }
    //check vertical
    for (iv = start_v + 1; iv <= mxv; iv++) {
        if (arr[iv][start_h] !== 0 || rsh[iv][start_h] > -1) {
            break;
        }
        ver++;
    }
    if (hor > ver || hor == ver) {
        shape.unshift({
            0: (hor),
            1: [start_v, start_h, 1, hor]
        });
        return true;
    } else if (ver > hor) {
        shape.push({
            0: (ver),
            1: [start_v, start_h, ver, 1]
        });
        return true;
    }
    return false;
}




//check SQUARE        
function check_sq(start_v, start_h) {
    if (arr[start_v + 1][start_h] !== 0) {
        return false;
    }
    if (arr[start_v][start_h + 1] !== 0) {
        return false;
    }
    var vd, hd, sv, sh, square;
    var hor = ver = 1;
    var mxv = maxv - 1;
    var mxh = maxh - 1;
    //CHECK DIAGONAL
    do {
        square = true;
        vd = start_v + ver;
        hd = start_h + hor;
        //diagonal OK
        if (arr[vd][hd] !== 0) {
            if (hor == 1) {
                if (ver == 1) {
                    return false;
                }
                square = false;
                break;
            }
        }
        //check horizontal
        for (sh = start_h; sh <= hd; sh++) {
            if (arr[vd][sh] !== 0) {
                square = false;
                break;
            }
        }
        if (square === false) break;
        //check vertical
        for (sv = start_v; sv <= vd; sv++) {
            if (arr[sv][hd] !== 0) {
                square = false;
                break;
            }
        }
        if (square === false) break;
        hor++;
        ver++;
    } while (square === true && vd < mxv && hd < mxh);
    //SQUARE OK
    if (hor > 1 && ver > 1 && hor == ver) {
        shape.push({
            0: (hor * ver),
            1: [start_v, start_h, ver, hor]
        });
    }
}


//check RECTANGLE
function check_rec(start_v, start_h) {
    var vd, hd, iv, ih, rect;
    var hor = ver = 1;
    var horb = 0;
    var mxv = maxv - 1;
    var mxh = maxh - 1;
    rect = true;
    vd = start_v + ver;
    hd = start_h + hor;

    //check horizontal
    if (start_h < maxh) {
        for (sh = start_h + 1; sh <= mxh; sh++) {
            if (arr[start_v][sh] !== 0 || rsh[start_v][sh] > -1) break;
            hor++;
        }
    }
    //check vertical
    if (start_v < maxv) {
        for (iv = start_v + 1; iv <= mxv; iv++) {
            if (arr[iv][start_h] !== 0 || rsh[iv][start_h] > -1) break;
            ver++;
        }
    }
    if (hor == 1 && ver == 1) return false;
    if (hor > ver || hor == ver) {
        shape.unshift({
            0: (hor),
            1: [start_v, start_h, 1, hor]
        });
        return true;
    } else {
        shape.push({
            0: (ver),
            1: [start_v, start_h, ver, 1]
        });
        return true;
    }
    return false;
}


//FIND LARGEST SHAPE
function occu() {
    var le = shape.length;
    for (var i = 0; i < le; i++) {
        var b = Math.max.apply(Math, shape.map(function (v) {
            return v[0];
        }));
        for (var j = 0; j < shape.length; j++) {
            if (shape[j][0] == b) break;
        }
        var c = shape.splice(j, 1);
        claim(c[0][1]);
    }
}


//CLAIM SHAPE
function claim(sh) {
    var iv, ih;
    for (iv = sh[0]; iv < sh[0] + sh[2]; iv++) {
        for (ih = sh[1]; ih < sh[1] + sh[3]; ih++) {
            if (rsv[iv][ih] > -1 || rsh[iv][ih] > -1) return false;
        }
    }
    for (iv = sh[0]; iv < sh[0] + sh[2]; iv++) {
        for (ih = sh[1]; ih < sh[1] + sh[3]; ih++) {
            rsv[iv][ih] = 0;
            rsh[iv][ih] = 0;
        }
    }
    rsv[sh[0]][sh[1]] = sh[2];
    rsh[sh[0]][sh[1]] = sh[3];
}

function pop_arr() {
    var em = [];
    em[0] = arr[0].concat();
    for (var i = 0; i < maxh; i++) {
        em[0][i] = -1;
    }
    for (i = 0; i < maxv; i++) {
        rsv[i] = em[0].concat();
        rsh[i] = em[0].concat();
    }
}