题解 - Vijos

1

Lifi LV 10 @ 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

prince_hao LV 10 @ 2009-11-09 18:42:55

难度3的水题

0

talent123 LV 9 @ 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

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

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

0

jacklv LV 10 @ 2009-10-18 21:35:59

浪费感情的一道水题

0

violethill LV 10 @ 2009-10-18 10:33:12

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

0

fp_ks LV 10 @ 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

sdfasd LV 9 @ 2009-08-25 16:18:13

开100*100数组+PUPPY=Unaccepted

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

诡异....

1s牛好帅啊!!

0

yxy LV 10 @ 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

盗亦有道 LV 8 @ 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

330459659 LV 10 @ 2009-08-01 15:58:19

汗｀｀｀

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

我交了几次４０的vj上老是过不了　什么１２８错误　还有两个希奇古怪的错，就去rq上交！

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

0

luyifan LV 10 @ 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

飘の★ LV 10 @ 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

zhfgogogo LV 10 @ 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

xiaobaibai LV 9 @ 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

tracy-henry LV 10 @ 2009-07-26 15:02:02

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

0

1s LV 10 @ 2009-08-09 11:45:11

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

0

yysyxxhh LV 8 @ 2009-07-26 10:02:50

n的范围是多少啊

0

wzk0731 LV 8 @ 2009-07-25 23:14:45

地心

0

ipip2005 LV 10 @ 2009-07-25 20:59:02

你用的是朴素BFS吗？

0

zhh1993 LV 10 @ 2009-07-27 11:00:34

不好意思，范围忘记了：n

题解

21 条题解

不听话的机器人

信息

状态

开发

支持

题解

21 条题解

不听话的机器人

信息

状态

开发

支持

还没有账户？

登录