在奇怪的表格上打印特定的数字

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

Run Code Online (Sandbox Code Playgroud)

第一行和第一行以0 1 2 3 4 5开始...在坐标(x,x)中始终为0,如您所见.在此之后的每个图块上,您必须放置在同一行或列上尚不存在的最小正数.就像在数独拼图中一样:在同一行和列上不能有两次数字.

现在我必须在给定的坐标(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;
}

Run Code Online (Sandbox Code Playgroud)

所以我该怎么做？这比我想象的要容易吗？