Kickstart Wiggle的解决方案

Question

我正试图为Kickstart的第1C轮优化我的摆动行走解决方案。

问题班尼刚买了一个新的可编程机器人。为了测试他的编码技巧，他将机器人放置在一个方格中，R行(从北到南编号为1到R)和C列(从西到东编号为1到C)。R行和c列中的正方形表示(r，c)。最初，机器人从正方形开始(SR，SC)。班尼会给机器人N个指令。每条指令都是N、S、E或W的指令，指示机器人分别向北、向南、向东或向西移动。如果机器人移动到它以前所在的正方形中，机器人将继续沿着相同的方向移动，直到到达以前没有的正方形为止。班尼永远不会给机器人一个指令，让它离开网格。你能帮班尼确定机器人在执行N个指令后将完成哪个方格吗？输入输入的第一行给出测试用例的数量，T测试用例紧随其后。每个测试用例从一行开始，分别包含五个整数N、R、C、SR和SC、指令数、行数、列数、机器人的起始行和起始列。然后，另一行包含N个字符的字符串；这些字符的第一行是班尼给机器人的第一条指令(上面描述了N、S、E或W中的一条)。输出每个测试用例，输出一行包含用例#x: r，其中x是测试用例编号(从1开始)，r是机器人完成的行，c是机器人完成的列。内存限制: 1GB。1≤T≤100。1≤R≤5×10 4。1≤C≤5×10 4。1≤SR≤R. 1≤SC≤C.指令不会导致机器人走出网格。测试集1(可见)时间限制:20秒。1≤N≤100。测试集2(隐藏)时间限制:60秒。1≤N≤5×10 4。

以下是我目前的解决方案：

def main():
    T = int(input())  # the number of test cases

    for case in range(1, T+1):
        N, R, C, r, c = map(int, input().split())
        instructions = input()  # string of N, S, E or W
        seen = {(r, c)}

        for i in instructions:
            if i == 'N':
                r -= 1
                while (r, c) in seen:
                    r -= 1
            elif i == 'S':
                r += 1
                while (r, c) in seen:
                    r += 1
            elif i == 'E':
                c += 1
                while (r, c) in seen:
                    c += 1
            else:  # 'W'
                c -= 1
                while (r, c) in seen:
                    c -= 1
            seen.add((r, c))

        print('Case #{}: {} {}'.format(case, r, c))


main()

如何表示网格中访问过的区域，以便更快地获取每个指令的目标单元格？

Answer 1

(一本简单的词典一旦你有了这个想法就可以了;)

def get_neighbor(r, c, i, neighbors):
    if (r, c, i) in neighbors:
        return neighbors[(r, c, i)]

    if i == 'N':
        return (r - 1, c)
    elif i == 'S':
        return (r + 1, c)
    elif i == 'E':
        return (r, c + 1)
    else:  # 'W'
        return (r, c - 1)


def link_neighbors(r, c, neighbors):
    north = get_neighbor(r, c, 'N', neighbors)
    south = get_neighbor(r, c, 'S', neighbors)
    east = get_neighbor(r, c, 'E', neighbors)
    west = get_neighbor(r, c, 'W', neighbors)

    neighbors[(*north, 'S')] = south
    neighbors[(*south, 'N')] = north
    neighbors[(*east, 'W')] = west
    neighbors[(*west, 'E')] = east


def main():
    T = int(input())  # the number of test cases

    for case in range(1, T+1):
        N, R, C, r, c = map(int, input().split())
        instructions = input()  # string of N, S, E or W
        neighbors = {}

        for i in instructions:
            link_neighbors(r, c, neighbors)
            r, c = get_neighbor(r, c, i, neighbors)  # new position

        print('Case #{}: {} {}'.format(case, r, c))


main()

Answer 2

我曾经参加过谷歌的扭动行走。

我已经将解决方案优化为\mathcal{O}(N\times logN)，但它仍然在“超过时限”。

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int t, n ,*arr, r , c, sr,sc,i=0;
    arr=(int*)malloc(5*sizeof(int));
    char temp;
    scanf("%d",&t);
    int z=1;
    while(z<=t)
    {
        int k=0;
        do {
            scanf("%d%c",arr+k,&temp);
            k++;
        } while(temp!='\n');
        n=*(arr);
        r=*(arr+1);
        c=*(arr+2);
        sr=*(arr+3);
        sc=*(arr+4);
        char *string;
        string =(char*)malloc(n*sizeof(char));
        int *grid = (int *)malloc(r * c * sizeof(int));
        int *northgrid =(int *)malloc(r * c * sizeof(int));
        int *southgrid = (int *)malloc(r * c * sizeof(int));
        int *eastgrid =(int *)malloc(r * c * sizeof(int));
        int *westgrid = (int *)malloc(r * c * sizeof(int));
        int current_sr,current_sc;
        *(grid + sr*c + sc)=1;
        for(int j=0; j<n; j++)
        {
            scanf("%c",string+j);
            current_sr = sr;
            current_sc = sc;

            if(*(string+j)=='N')
            {
                do
                {
                    if(*(northgrid + sr*c + sc)==0)
                    {

                        sr--;

                    }
                    else if(*(northgrid + sr*c + sc)!=0)
                    {
                        while(*(northgrid + sr*c + sc)!=0)
                        {
                            sr=*(northgrid + sr*c + sc);
                        }
                    }
                } while(*(grid + sr*c + sc)==1);
                *(grid + sr*c + sc)=1;
                *(southgrid+ sr*c + sc)=current_sr;
                *(northgrid+current_sr*c+current_sc)=sr;
            }
            else if(*(string+j)=='S')
            {
                do
                {
                    if(*(southgrid + sr*c + sc)==0)
                    {

                        sr++;

                    }
                    else if(*(southgrid + sr*c + sc)!=0)
                    {
                        while(*(southgrid + sr*c + sc)!=0)
                        {
                            sr=*(southgrid + sr*c + sc);
                        }
                    }
                } while(*(grid + sr*c + sc)==1);
                *(grid + sr*c + sc)=1;
                *(northgrid+ sr*c + sc)=current_sr;
                *(southgrid+current_sr*c+current_sc)=sr;
            }
            else if(*(string+j)=='E')
            {
                do
                {
                    if(*(eastgrid + sr*c + sc)==0)
                    {

                        sc++;

                    }
                    else if(*(eastgrid + sr*c + sc)!=0)
                    {
                        while(*(eastgrid + sr*c + sc)!=0)
                        {
                            sr=*(eastgrid + sr*c + sc);
                        }
                    }
                } while(*(grid + sr*c + sc)==1);
                *(grid + sr*c + sc)=1;
                *(westgrid+ sr*c + sc)=current_sc;
                *(eastgrid+current_sr*c+current_sc)=sc;
            }
            else if(*(string+j)=='W')
            {
                do
                {
                    if(*(westgrid + sr*c + sc)==0)
                    {

                        sc--;

                    }
                    else if(*(westgrid + sr*c + sc)!=0)
                    {
                        while(*(westgrid + sr*c + sc)!=0)
                        {
                            sc=*(westgrid + sr*c + sc);
                        }
                    }
                } while(*(grid + sr*c + sc)==1);
                *(grid + sr*c + sc)=1;
                *(eastgrid+ sr*c + sc)=current_sc;
                *(westgrid+current_sr*c+current_sc)=sc;
            }
            // printf("Values are: %d , %d",sr,sc);
        }
        printf("Case #%d: %d %d\n",z,sr,sc);

        z++  ;
    }
}