34 条题解

  • 3
    @ 2016-08-02 19:23:04
        #include <cstdio>
    #include <cstring>
    #include <iostream>
    
    using namespace std;
    
    const int Maxn=51;
    
    int n,m,x,y,t,ans[Maxn][Maxn];
    char map[Maxn][Maxn];
    string dir;
    
    void work(int a)
    {
        int x1,y1;
        
            if(dir=="NORTH") {x1=x-1;while(ans[x1][y]<a&& x1>0&&map[x1][y]!='X'){ans[x1][y]=a;x1--;}}
        else if(dir=="WEST") {y1=y-1;while(ans[x][y1]<a&& y1>0&&map[x][y1]!='X'){ans[x][y1]=a;y1--;}}
        else if(dir=="SOUTH"){x1=x+1;while(ans[x1][y]<a&&x1<=n&&map[x1][y]!='X'){ans[x1][y]=a;x1++;}}
        else if(dir=="EAST") {y1=y+1;while(ans[x][y1]<a&&y1<=m&&map[x][y1]!='X'){ans[x][y1]=a;y1++;}}
    }
    
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                cin>>map[i][j]; 
                if(map[i][j]=='*')
                    x=i,y=j;
            }
                
        memset(ans,-1,sizeof(ans));
        
        ans[x][y]=0;
        
        scanf("%d",&t);
        
        for(int k=1;k<=t;k++){
            cin>>dir;
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                    if(ans[i][j]==k-1){
                        x=i;y=j;
                        work(k);
                    }   
        }
        
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(ans[i][j]==t)printf("*");
                else if(map[i][j]=='X')printf("X");
                else printf(".");
            }
            printf("\n");
        }
    }
    

    宽搜 Codevs逃跑的拉尔夫

    • @ 2016-08-04 15:48:12

      不好意思 我没看好他 让大家受惊了

  • 0
    @ 2015-09-24 21:03:30

    需要动态规划吗?……
    #include<cstdio>
    #include<iostream>
    #include<cstdlib>
    using namespace std;
    int k,c,n,i,j,l;
    char map[201][201],dir[1001][6];
    void go(int now){
    if(now==n+1)return;
    switch(dir[now][0]){
    case 'E':{
    for(i=1;i<=k;++i)
    for(j=1;j<=c;++j)
    if(map[i][j]=='*'){
    map[i][j]='.';
    for(l=j+1;map[i][l]!='X'&&l<=c;++l)map[i][l]=',';
    }
    for(i=1;i<=k;++i)
    for(j=1;j<=c;++j)
    if(map[i][j]==',')map[i][j]='*';
    break;
    }
    case 'S':{
    for(i=1;i<=k;++i)
    for(j=1;j<=c;++j)
    if(map[i][j]=='*'){
    map[i][j]='.';
    for(l=i+1;map[l][j]!='X'&&l<=k;++l)map[l][j]=',';
    }
    for(i=1;i<=k;++i)
    for(j=1;j<=c;++j)
    if(map[i][j]==',')map[i][j]='*';
    break;
    }
    case 'W':{
    for(i=k;i>=1;--i)
    for(j=c;j>=1;--j)
    if(map[i][j]=='*'){
    map[i][j]='.';
    for(l=j-1;map[i][l]!='X'&&l>=1;--l)map[i][l]=',';
    }
    for(i=1;i<=k;++i)
    for(j=1;j<=c;++j)
    if(map[i][j]==',')map[i][j]='*';
    break;
    }
    case 'N':{
    for(i=k;i>=1;--i)
    for(j=c;j>=1;--j)
    if(map[i][j]=='*'){
    map[i][j]='.';
    for(l=i-1;map[l][j]!='X'&&l>=1;--l)map[l][j]=',';
    }
    for(i=1;i<=k;++i)
    for(j=1;j<=c;++j)
    if(map[i][j]==',')map[i][j]='*';
    break;
    }
    }
    go(now+1);
    }
    int main(){
    freopen("in.txt","r",stdin);
    scanf("%d%d",&k,&c);
    for(i=1;i<=k;++i)
    for(j=1;j<=c;++j)cin>>map[i][j];
    scanf("%d",&n);
    for(i=1;i<=n;++i)scanf("%s",&dir[i]);
    go(1);
    for(i=1;i<=k;++i){
    for(j=1;j<=c;++j)printf("%c",map[i][j]);
    printf("\n");
    }
    }
    测试数据 #0: Accepted, time = 46 ms, mem = 560 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 564 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 560 KiB, score = 10
    测试数据 #3: Accepted, time = 17 ms, mem = 564 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 564 KiB, score = 10
    测试数据 #5: Accepted, time = 4 ms, mem = 560 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 560 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 564 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 564 KiB, score = 10
    测试数据 #9: Accepted, time = 31 ms, mem = 564 KiB, score = 10

  • 0
    @ 2010-07-08 15:41:06

    话说现在机器太神了,最裸的算法(估计10^7,K次fillchar)居然都能秒,害我担心过不去想了半天……

  • 0
    @ 2010-07-05 11:39:51

    一开始用裸的DFS只得30分,后来在楼下大牛的提醒下用f[dep,x,y]表示第dep次转弯,点[x,y]是否到过,如果到过,那么这一次的情况就会重复,当然不要了。

    记忆化搜索,效率很高!

  • 0
    @ 2009-10-06 21:14:32

    数据太弱了- -~。

    N^3*K都能过。。。。

  • 0
    @ 2009-09-30 22:51:00

    编译通过...

    ├ 测试数据 01:运行时错误...|错误号: 216

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

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

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

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

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

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

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

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

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

    为什么这么没rp

  • 0
    @ 2009-09-16 00:27:28

    不吉利啊!!!第444人通过啊!!!

    Flag   Accepted

    题号   P1226

    类型(?)   其它

    通过   444人

    提交   1619次

    通过率   27%

    难度   1

    题解:

    http://lifeich1.spaces.live.com/blog/cns!9AB465A9D807BE22!192.entry

  • 0
    @ 2009-08-16 15:20:17

    编译失败...|错误号:-1

    这个是什么状况= =

    128是什么错误。。。

  • 0
    @ 2009-07-09 21:32:53

    DFS秒杀

  • 0
    @ 2009-07-01 16:31:04

    DFS + 判重 = 秒杀

  • 0
    @ 2009-05-19 20:21:00

    BFS一次AC

  • 0
    @ 2009-05-18 15:22:38

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    DP秒杀

    f表示能否到达(i,j),再滚动就AC了

  • 0
    @ 2009-04-06 01:16:11

    bfs!

    没加判重:

    编译通过...

    ├ 测试数据 01:答案错误...

     ├ Hint: Made By DdsNet For Vijos ├ 标准行输出

     ├ 错误行输出

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

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

    ├ 测试数据 04:运行时错误...|错误号: -1073741819

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

    ├ 测试数据 06:运行时错误...|错误号: -1073741819

    ├ 测试数据 07:运行时错误...|错误号: -1073741819

    ├ 测试数据 08:运行时错误...|错误号: -1073741819

    ├ 测试数据 09:运行时错误...|错误号: -1073741819

    ├ 测试数据 10:答案错误...

     ├ Hint: Made By DdsNet For Vijos ├ 标准行输出

     ├ 错误行输出

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

    Unaccepted 有效得分:30 有效耗时:0ms

    加了一个判重:

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    提示一下怎么判重:

    开一个bool数组:done[i][j][k]

    它表示在第i次转弯是否达到过(j,k)这个点,如果到达过了,就不用再扩展这个点了!

  • 0
    @ 2009-02-05 12:05:48

    搞一个队列按要求扩展。

    为了节省空间,建议建两个队列滚动着做。

    提醒出现莫名其妙错误的同学:两个队列要区分清楚,头尾指针不要乱。

  • 0
    @ 2009-01-28 19:21:22

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

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

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

    运气不错…… 数据不够强……

    模拟…… 结果有点诡异 交了3次AC 前两次都是复制的四部分中变量搞错了 太麻烦了 一会横一会竖 头昏。

    策略详细解释下 就是如果向右 就找出 每行最靠右边的*点 然后此点左边第一个到向左延伸到0或者遇到X的点都为*可能的。用了大概5重的while循环……变量N多。

    如果向下 就找出毎(列!)最靠上边的点 然后此点下一个到向下延伸遇到的0和X点都为*可能的。接受多少命令 就把所有的*点都按策略走一次…… 最后输出走完的最后结果就OK。

    case 上下左右4种情况 上下和左右是两种分别可以复制的但是复制之后千万注意各种变量的改变……囧 太烦了 不过还是改出来了 自己做了几个测试数据。

    WA了给的答案与实际情况不符也要注意 因为我这个策略是不会改变X点的一开始看到答案让我郁闷好久。

  • 0
    @ 2009-01-11 13:44:37

    (滚动数组)模拟就ok了

  • 0
    @ 2008-11-13 21:53:22

    实际图与输入文件反一下(描述里使用的是数学上的坐标)

  • 0
    @ 2008-10-28 17:14:46

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    \\\\\\\\\\\\\\\\\\\\\

    BFS ....

  • 0
    @ 2008-10-07 21:25:35

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    DP

  • 0
    @ 2008-09-30 00:31:49

    BFS??

    不是BFS吧..

信息

ID
1226
难度
5
分类
动态规划 点击显示
标签
(无)
递交数
450
已通过
163
通过率
36%
被复制
5
上传者