题解 - Vijos

3

sssSSSay LV 10 @ 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逃跑的拉尔夫

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

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

0

PatenaireJunior LV 7 @ 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

zhh1993 LV 10 @ 2010-07-08 15:41:06

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

0

xuxun LV 10 @ 2010-07-05 11:39:51

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

记忆化搜索，效率很高！

0

KevinH LV 9 @ 2009-10-06 21:14:32

数据太弱了- -~。

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

0

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

李肥888 LV 10 @ 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

Melody1992 LV 10 @ 2009-08-16 15:20:17

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

这个是什么状况= =

128是什么错误。。。

0

永远的波拿巴 LV 10 @ 2009-07-09 21:32:53

DFS秒杀

0

木子日匀 LV 10 @ 2009-07-01 16:31:04

DFS + 判重 = 秒杀

0

yxy LV 10 @ 2009-05-19 20:21:00

BFS一次AC

0

怪盗~基德 LV 10 @ 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

唐钰小宝 LV 10 @ 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

oimaster LV 10 @ 2009-02-05 12:05:48

搞一个队列按要求扩展。

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

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

0

破晓Daybreak LV 8 @ 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

cgy4ever LV 10 @ 2009-01-11 13:44:37

(滚动数组)模拟就ok了

0

tangdongjian LV 8 @ 2008-11-13 21:53:22

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

0

lyyztt67 LV 4 @ 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

c7 LV 3 @ 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

Bobby_Z LV 7 @ 2008-09-30 00:31:49

BFS??

不是BFS吧..

题解

34 条题解

拯救世界-拯救博士

信息

状态

开发

支持

题解

34 条题解

拯救世界-拯救博士

信息

状态

开发

支持

还没有账户？

登录