时间戳

首页 > 解决方案 > 如何在这个宾果游戏程序中避免 TLE？

c - 如何在这个宾果游戏程序中避免 TLE？

问题描述

我正在用 C 语言编写一个宾果游戏程序，当在线评委给我巨大的宾果板（例如 1 人 256*256 板或 6 人 150*150 板）时，它正在“超过时间限制”。如何优化我的代码以避免发生 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（玩家人数、棋盘边长、姓名、棋盘、选择的数字） John 1 2 3 4 5 6 7 8 9 May 1 2 3 4 5 6 7 8 9 1 2 4 8 6 3 9 5 7 预期输出：（有人玩宾果游戏时的人数，获胜玩家的姓名） 3 John May

标签： c

解决方案

照原样，您的算法提供了相当多的优化机会：

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!
        }
    }
}

推荐阅读