c - 如何在宾果游戏中避免 TLE？

Question

我正在用 C 语言编写一个宾果游戏程序，该程序出现“时间限制”当在线评委给我巨大的宾果游戏板(例如 256*256 板 1 人或 150*150 板 6 人)时，我超出了”。我如何优化我的代码以避免 TLE 发生？(对不起英语不好)

我的程序获取所有名称和板，当给出新编号时，它会扫描每个板并标记编号。然后它会检查玩家是否有必要进行宾果游戏。我尝试添加尽可能多的中断；我尽了最大的努力来减少循环次数，但它仍然运行了 1070 毫秒。

#include <stdio.h>

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    char players[n][64];    
    int board[n][m][m]; 
    for(int i=0;i<n;i++){            //input every player's name & board
        scanf("%s",&players[i]);
        for(int j=0;j<m;j++){
            for(int k=0;k<m;k++){
                scanf("%d",&board[i][j][k]);
            }
        }
    }
    int number;
    int foundx, foundy;
    int ifBreak = 0;
    int sum;
    int winNumber;
    int winCount = 0;
    int winners[n];
    for(int i=0;i<m*m && winCount==0;i++){
        scanf("%d",&number);            //input the numbers chosen to be marked         
        for(int j=0;j<n;j++){
            ifBreak = 0;
            sum = 0;

            for(int k=0;k<m && ifBreak==0;k++){  //mark -1 on the number chosen
                for(int l=0;l<m;l++){
                    if(board[j][k][l] == number){
                        board[j][k][l] = -1;
                        foundx = k;
                        foundy = l;
                        ifBreak = 1;
                        break;
                    }
                }
            }
            ifBreak = 0;

            //inspect horizontal line
            for(int k=0;k<m && ifBreak==0 && i>=m-1;k++){  
                if(board[j][foundx][k] != -1)
                    break;
                sum += board[j][foundx][k];
            }
            if(sum == -m){  
                winNumber = number;
                winners[winCount] = j;
                winCount++;
                ifBreak = 1;                  
            }
            sum = 0;

            //inspect vertical line
            for(int k=0;k<m && ifBreak==0 && i>=m-1;k++){  
                if(board[j][k][foundy] != -1)
                    break;
                sum += board[j][k][foundy];
            }
            if(sum == -m){  
                winNumber = number;
                winners[winCount] = j;
                ifBreak = 1;                
                winCount++;
            }
            sum = 0;

            //inspect cross line
            for(int k=0;k<m && ifBreak==0 && i>=m-1 && foundx-foundy==0;k++){  
                if(board[j][k][k] != -1)
                    break;
                sum += board[j][k][k];
            }
            if(sum == -m && ifBreak==0){
                winNumber = number;
                winners[winCount] = j;
                winCount++;
                ifBreak = 1;        
            }
            sum = 0;

            //inspect cross line
            for(int k=0;k<m && ifBreak==0 && i>=m-1 && foundx+foundy==m-1;k++){ 
                if(board[j][k][m-1-k] != -1) 
                    break;
                sum += board[j][k][m-1-k];
            }
            if(sum == -m && ifBreak==0){
                winNumber = number;
                winners[winCount] = j;
                winCount++;
                ifBreak = 1;        
            }
            sum = 0;

        }
    }
    printf("%d",winNumber);

    for(int p=0;p<winCount;p++){
        printf(" %s",players[winners[p]]);
    }
}

当进行上述两个测试时，我希望程序能够在一秒钟内运行。

输入示例:2 3(玩家数量、棋盘边长、姓名、棋盘、选择的数字)约翰1 2 34 5 67 8 9可能1 2 34 5 67 8 91 2 4 8 6 3 9 5 7预期输出:(有人宾果时的数字，获胜玩家的名字)3 约翰·梅

Answer 1

您的算法本身提供了很多优化机会:

for(int k=0;k<m && ifBreak==0;k++)
{
    for(int l=0;l<m;l++)
    {
        if(...)
        {
            ifBreak = 1;
            break;
        }
    }
}

此代码会在每次循环运行的外循环中产生额外的条件分支。您可以使用goto来避免这种情况:

for(int k=0; k<m; k++)
{
    for(int l=0; l<m; l++)
    {
        if(...)
        {
            goto LoopExitN;
        }
    }
}
LoopExitN:
// next loop...

然后你就有了多个循环，每个循环一个接一个地运行——并且每个循环都有自己的停止条件比较。如果将所有这些循环合并为单个循环，则可以省去许多这些检查:

for(int k=0; k<m; k++)
{
    for(int l=0; l<m; l++)
    {
        // check for lines:       board[k][l]
        // check for columns:     board[l][k]
    }
    // check for first diagonal:  board[k][k]
    // check for second diagonal: board[k][m-k]
}

唯一的原因是，提前退出条件变得更加困难；如果出现故障，您可能会跟踪每一行、每一列和两条对角线，如果所有这些跟踪都被伪造，您就会退出。为了提高效率，每次伪造其中一个轨道时，总计数都会减少 2*m + 2 - 并在该计数变为零时立即退出循环。不过，如果你真的变得更快，你还必须进行评估。

但是现在让我们再次退后一步:您是否注意到，按照您的算法，您正在使用每个新选择的数字重新评估每一行、每一列和每条对角线？这是相当多的工作要做。而正是在这里，您在大多数情况下都可以安全:您应该避免这些重新计算!如何？非常简单:跟踪完成行/列/诊断还缺少多少数字:

for(int k=0; k<m; k++)
{
    for(int l=0; l<m; l++)
    {
        if(board[k][l] == number)
        {
            if
            (
                --rows[k] == 0 || --columns[l] == 0
                || (l == k && --diagnoal1 == 0)
                || (l == m - k - 1 && --diagnoal2 == 0)
            )
            {
                // we have a winner!
                goto CurrentPlayerCompleted;
            }
        }
    }
}

当然，您可以使用 m... 初始化所有这些行/列/对角线...

编辑:由于这些修改似乎还不够:更改板的表示形式!不要使用 [m][m] 数组(有效地将位置映射到数字)，而是使用查找表数字到位置!

这样您就不需要内部的双循环(但您将保留上面的行/列/对角线字段!):

for(int i = 0; i < m * m && winCount == 0; i++)
{
    for(int j = 0; j < n; j++)
    {
        // possibly need to check if the number is contained in board at all

        // possibly need to apply some hash function, for now, assuming
        // that an array for all numbers is sufficient, leaving the rest to you
        struct position pos = board[number];

        if
        (
            --rows[pos.row] == 0 || --columns[pos.column] == 0
            || (pos.column == pos.row && --diagonal1 == 0)
            || (pos.column == m - pos.row - 1 && --diagnoal2)
        )
        {
            // we have a winner!
        }
    }
}