21 条题解

  • 1
    @ 2019-08-31 15:41:01

    记录到达每个点4个方向的最小删除数目。

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    
    using namespace std;
    
    int n,m;
    bool ma[102][102]={0};
    int px[4]={-1,0,1,0};
    int py[4]={0,-1,0,1};
    int dp[2][102][102][4]={0};
    
    int main()
    {
        int i,j,k,x,y;
        char c;
        cin>>n>>m>>x>>y;
        fflush(stdin);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                cin>>c;
                if(c=='.')
                {
                    ma[i][j]=true;
                }
            }
        }
        memset(dp,62,sizeof(dp));
        dp[0][x][y][0]=0;
        string order;
        for(i=0;i<m;i++)
        {
            cin>>order;
            if(order[0]=='F')
            {
                for(x=1;x<=n;x++)
                {
                    for(y=1;y<=n;y++)
                    {
                        for(j=0;j<4;j++)
                        {
                            dp[(i+1)%2][x][y][j]=dp[i%2][x][y][j]+1;
                            if(ma[x][y])
                            {
                                dp[(i+1)%2][x][y][j]=min(dp[(i+1)%2][x][y][j],dp[i%2][x-px[j]][y-py[j]][j]);
                            }
                        }
                    }
                }
            }
            else if(order[0]=='B')
            {
                for(x=1;x<=n;x++)
                {
                    for(y=1;y<=n;y++)
                    {
                        for(j=0;j<4;j++)
                        {
                            dp[(i+1)%2][x][y][j]=dp[i%2][x][y][j]+1;
                            if(ma[x][y])
                            {
                                dp[(i+1)%2][x][y][j]=min(dp[(i+1)%2][x][y][j],dp[i%2][x+px[j]][y+py[j]][j]);
                            }
                        }
                    }
                }
            }
            else if(order[0]=='L')
            {
                for(x=1;x<=n;x++)
                {
                    for(y=1;y<=n;y++)
                    {
                        for(j=0;j<4;j++)
                        {
                            dp[(i+1)%2][x][y][(j+1)%4]=min(dp[i%2][x][y][(j+1)%4]+1,dp[i%2][x][y][j]);
                        }
                    }
                }
            }
            else if(order[0]=='R')
            {
                for(x=1;x<=n;x++)
                {
                    for(y=1;y<=n;y++)
                    {
                        for(j=0;j<4;j++)
                        {
                            dp[(i+1)%2][x][y][(j+3)%4]=min(dp[i%2][x][y][(j+3)%4]+1,dp[i%2][x][y][j]);
                        }
                    }
                }
            }
        }
        x=1e9;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                for(k=0;k<4;k++)
                {
                    x=min(dp[m%2][i][j][k],x);
                }
            }
        }
        cout<<x<<endl;
        return 0;
    }
    
  • 0
    @ 2009-11-09 18:42:55

    难度3的水题

  • 0
    @ 2009-11-02 23:33:05

    ms很少有秒杀的...

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    不信的在“状态”里找talent123...100分...0ms

    • @ 2015-12-19 22:28:12

      Orz...大神您是怎么做到的

  • 0
    @ 2009-10-18 21:35:59

    浪费感情的一道水题

  • 0
    @ 2009-10-18 10:33:12

    第一次碰sunny没有最后一个点tle 第二次就碰Edogawa Conana了

  • 0
    @ 2009-08-30 21:48:24

    我很肯定的告诉你们这题的数据有问题!输入说有M条命令,实际上根本就没有M条!大家改下应该就可以AC了!

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 25ms

    ├ 测试数据 09:答案正确... 56ms

    ├ 测试数据 10:答案正确... 88ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:169ms

  • 0
    @ 2009-08-25 16:18:13

    开100*100数组+PUPPY=Unaccepted

    开200*200数组+PUPPY+PUPPY没有抽筋=AC

    诡异....

    1s牛好帅啊!!

  • 0
    @ 2009-08-07 22:38:31

    题A了,我挂了

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 41ms

    ├ 测试数据 07:答案正确... 166ms

    ├ 测试数据 08:答案正确... 275ms

    ├ 测试数据 09:答案正确... 431ms

    ├ 测试数据 10:答案正确... 650ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:1563ms

    搞了一个晚上,编了3个程序

    其中还把“FORWARD”打成了“TOWARD”

  • 0
    @ 2009-08-06 21:15:39

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 25ms

    ├ 测试数据 08:答案正确... 56ms

    ├ 测试数据 09:答案正确... 119ms

    ├ 测试数据 10:答案正确... 197ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:397ms

    可惜 无法秒杀!!!膜拜中

  • 0
    @ 2009-08-01 15:58:19

    汗```

    题目的数据范围是不是有错啊!

    我交了几次40的vj上老是过不了 什么128错误 还有两个希奇古怪的错,就去rq上交!

    结果出现了一个普通保护错误,然后我把数组开大了一点 就AC了!

  • 0
    @ 2009-07-30 14:56:30

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 25ms

    ├ 测试数据 07:答案正确... 134ms

    ├ 测试数据 08:答案正确... 228ms

    ├ 测试数据 09:答案正确... 369ms

    ├ 测试数据 10:答案正确... 494ms

    菜鸟我太菜了,这么慢。何况0秒

  • 0
    @ 2009-07-28 22:34:20

    其实、、dp不难、、

    但是要秒杀、、、真的很难、、

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 25ms

    ├ 测试数据 08:答案正确... 72ms

    ├ 测试数据 09:答案正确... 134ms

    ├ 测试数据 10:答案正确... 259ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:490ms

  • 0
    @ 2009-07-26 22:14:09

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 9ms

    ├ 测试数据 07:答案正确... 119ms

    ├ 测试数据 08:答案正确... 212ms

    ├ 测试数据 09:答案正确... 322ms

    ├ 测试数据 10:答案正确... 494ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:1156ms

    那个初始位置输入的应该是(y0,x0)......

    叫我WA了5次

  • 0
    @ 2009-07-26 21:13:00

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 9ms

    ├ 测试数据 09:答案正确... 41ms

    ├ 测试数据 10:答案正确... 88ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:138ms

    就是不让我秒杀...

  • 0
    @ 2009-07-26 15:02:02

    lx的1000MS有我的风范= =||

  • 0
    @ 2009-08-09 11:45:11

    其实挺简单,状态f[i][x][y][d]表示前i条命令执行完之后,机器人在位置(x,y),面朝方向d时,最少需要去掉的命令数。策略只有简单的两种:去掉当前这一条或者没有去掉。用滚动数组减少空间消耗。数据范围:迷宫的边长 N

  • 0
    @ 2009-07-26 10:02:50

    n的范围是多少啊

  • 0
    @ 2009-07-25 23:14:45

    地心

  • 0
    @ 2009-07-25 20:59:02

    你用的是朴素BFS吗?

  • 0
    @ 2009-07-27 11:00:34

    不好意思,范围忘记了:n

信息

ID
1592
难度
6
分类
动态规划 点击显示
标签
(无)
递交数
425
已通过
114
通过率
27%
被复制
2
上传者