c - UVA 问题 12503 给 TLE

Question

我正在尝试解决 UVA 在线判断上的 12503 问题。我想我已经找到了解决方案，但它给了我 TLE。这是问题所在:

你有一个机器人站在 x 轴的原点上。机器人将得到一些指令。你的任务是在执行完所有指令后预测它的位置。

• LEFT:向左移动一个单位(p减1，p为机器人移动前的位置)

• RIGHT:向右移动一个单位(p 增加 1)

• 与 i 相同:执行与第 i 条指令相同的操作。保证i是正数

输入整数不大于在此之前的指令数。第一行包含测试用例数量 T(T <= 100)。每个测试用例都以一个整数 n (1 <= n <= 100) 开头，即指令数。以下 n 行中的每一行都包含一条指令。

输出

对于每个测试用例，打印机器人的最终位置。请注意，在处理完每个测试用例之后，机器人应该复位到原点。

示例输入

2

3

LEFT

RIGHT

SAME AS 2

5

LEFT

SAME AS 1

SAME AS 2

SAME AS 1

SAME AS 4

Sample Output

1

-5

这是我在 C 中的代码:

#include <stdio.h>

char com[102][20];
int command(char comd[], int pos);

int main() {
    int t;
    int pos;
    int i, n;
    char tmp[20];

    scanf("%d", &t);
    for(i = 0; i < t; i++) {
        scanf("%d", &n);

        int j;

        pos = 0;
        for (j = 0; j < n; j++) {
            gets(com[j]);
            if (strcmp(com[j], "LEFT") == 0)
                pos--;
            else if(strcmp(com[j], "RIGHT") == 0)
                pos++;
            else {
                pos = command(com[j], pos);
            }
        }

        printf("%d\n", pos);
    }

    return 0;
}

int command(char comd[], int pos) {
    if (strcmp(comd, "LEFT") == 0) {
        pos--;
        return pos;
    }
    else if (strcmp(comd, "RIGHT") == 0) {
        pos++;
        return pos;
    }
    else{
        int a = atoi(&comd[8]);

        return command(com[a-1], pos);
    }
}

为什么这段代码给出 TLE 有什么建议吗？

Answer 1

在 int command(char comd[], int pos) 函数中，您在最后一行使用了递归调用。这可能会导致 TLE。

要解决此问题，您可以使用另一个数组来存储机器人执行命令所走的步数。您只需稍后访问数组的索引即可获取上一个命令的步骤。

下面是我会怎么做-

#include <stdio.h>
#include <string.h>

int move[110];
int getMove(char inp[], int);

int main()
{
    int t, n;
    char inp[50];

    scanf(" %d ",&t);
    while(t--)
    {
        scanf(" %d ",&n);

        int i, pos = 0;
        for(i = 0; i < n; i++)
        {
            gets(inp);
            pos += getMove(inp, i);
        }

        printf("%d\n",pos);
    }

    return 0;
}

int getMove(char inp[], int i)
{
    if(inp[0]=='S')
    {
        int j;
        sscanf(strrchr(inp,' ')," %d",&j);
        move[i] = move[j - 1];
    }
    else
    {
        move[i] = (inp[0] == 'L') ? -1 : 1;
    }
    return move[i];
}