c++ - 在一张奇怪的 table 上打印一个特定的数字

Question

我有一个表格，其中包含以这种方式排列的非负整数:表格中的每个元素都是未出现在其左侧或上方的最小值。这是 6x6 网格的示例:

0 1 2 3 4 5
1 0 3 2 5 4
2 3 0 1 6 7
3 2 1 0 7 6
4 5 6 7 0 1
5 4 7 6 1 0 

第一行和第一列以 0 1 2 3 4 5 开头...如您所见，在坐标 (x,x) 中始终为 0。在那之后的每个图 block 上，您必须放置在同一行或列上尚不存在的最小正数。很像数独游戏:同一行和同一列不能出现两次数字。

现在我必须打印给定坐标 (y,x) 中的数字。例如 [2, 5] = 5

我想出了一个可行的解决方案，但它占用太多内存和时间，而且我只知道还有另一种方法可以做到这一点。我的时间限制是 1 秒，我必须找到数字的坐标可以达到 (1000000, 1000000)。

这是我目前的代码:

#include <iostream>
#include <vector>

int main()
{
    int y, x, grid_size;
    std::vector< std::vector<int> > grid;

    std::cin >> y >> x; // input the coordinates we're looking for

    grid.resize(y, std::vector<int>(x, 0)); // resize the vector and initialize every tile to 0

    for(int i = 0; i < y; i++)
        for(int j = 0; j < x; j++)
        {
            int num = 1;

            if(i != j) { // to keep the zero-diagonal

                for(int h = 0; h < y; h++)
                    for(int k = 0; k < x; k++) { // scan the current row and column
                        if(grid[h][j] == num || grid[i][k] == num) { // if we encounter the current num
                            num++;                                   // on the same row or column, increment num
                            h = -1; // scan the same row and column again
                            break;
                        }
                    }

                grid[i][j] = num; // assign the smallest number possible to the current tile

            }
        }

    /*for(int i = 0; i < y; i++) {            // print the grid
        for(int j = 0; j < x; j++)            // for debugging
            std::cout << grid[i][j] << " ";   // reasons

        std::cout << std::endl;
    }*/

    std::cout << grid[y-1][x-1] << std::endl; // print the tile number at the requested coordinates
    //system("pause");
    return 0;
}

那我该怎么办呢？这比我想象的要容易吗？

Answer 1

总结一下您的问题:您有一个表，其中每个元素都是未出现在其左侧或上方的最小非负整数。您需要找到位于 (x,y) 位置的元素。

结果非常简单:如果 x和 y是从 0 开始的，那么 (x,y) 处的元素是 x XOR y .这与您发布的表格相匹配。我有 verified实验性地用于 200x200 的表格。

证明:

很容易看出相同的数字不会在同一行或同一列出现两次，因为如果 x₁^y = x₂^y 那么必然x₁=x₂.

看到x^y是最小的:让 a是一个小于 x^y 的数字.让i是最左边位的索引(从右边开始)，其中 a不同于 x^y . i a 的第 1 位必须为 0 且 i x^y 的第 1 位必须为 1。

因此，x或 y i 中必须有 0第 位。假设 WLOG 是 x有 0。代表 x和 y作为:

x = A0B
y = C1D

其中 A、B、C、D 是位序列，B 和 D 是 i位长。由于 a 的最左边位与x^y中的相同:

a^x = C0E

其中 E 是 i 的序列位。所以我们可以看到 a^x < y . (a^x) 中出现的值同一列的第行是:(a^x)^x = a .所以值 a必须已经出现在同一行(或列，如果它是 y 在 i 位中有 0)。对于小于 x^y 的任何值都是如此, 所以 x^y确实是最小可能值。