题解 - Vijos

3

猫粮寸断 LV 10 @ 2018-11-06 20:46:42

//这道题算是dfs的板子题吧
//比较新的地方就是奇偶剪这个东西
//因为每一秒都必须移动，所以步数与距离的奇偶性不一样是无法到达的
//比如距离为2，让你走5步肯定是到不了的
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
char map[9][9]; 
int n,m,t,x,y,flag,pan[9][9];
int dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};
void dfs(int nx,int ny,int now)
{
    if(abs(nx-x)+abs(ny-y)>t-now)           //可行性剪枝 
     return ;
    if(int(abs(nx-x)+abs(ny-y))%2!=int(t-now)%2)        //奇偶性剪枝 
     return ;
    if(now==t)
     {
        if(nx==x&&ny==y)
         flag=1;
        return ;
     }
    for(int i=1;i<=4;i++)
    {
        int px=nx+dx[i];
        int py=ny+dy[i];
        if(px>0&&px<=n&&py>0&&py<=m)
         if(map[px][py]=='*'||(map[px][py]=='D'&&now==t-1))
          if(!pan[px][py])
          {
            pan[px][py]=1;
            dfs(px,py,now+1);
            pan[px][py]=0;
          } 
          if(flag)      //此处剪枝非常关键！！！ 
           return ;
    }
}
int main()
{
    while(1)
    {
        scanf("%d%d%d",&n,&m,&t);
        if(n==0)
         break;
        int i,j;
        flag=0;
        for(i=1;i<=n;i++)
         for(j=1;j<=m;j++)
          {
           scanf(" %c",&map[i][j]);
           if(map[i][j]=='D')
            {
                x=i;
                y=j;
            }
          }
        dfs(1,1,0);
        if(flag)
         cout<<"Yes"<<endl;
        else
         cout<<"No"<<endl;
    }
    return 0;
}

1

bi1_1 LV 9 @ 2009-11-07 16:12:51

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

COPY fjxmlhx

奇偶剪就是如果当前点(i,j)满足(i+j+k)mod2(x+y) mod 2则剪

x y是目标点

k是剩余时间

自己做的是DPS,其他的剪枝作用不大

0

Vijos永远NB (郑灏轩) LV 10 @ 2022-01-09 14:28:37

《真 ·js 市》
注：js=精神

0

Lifi LV 10 @ 2019-08-28 17:43:08

奇偶剪枝真的秒啊，加两行代码就能过：

if((abs(a-x)+abs(b-y))%2!=(t-d)%2)
{
    return;
}

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

int n,m,t,a,b;
char ma[7][7];
bool vis[7][7];
bool ans;

int abs(int x)
{
    if(x<0)
    {
        return -x;
    }
    else
    {
        return x;
    }
}

void dfs(int x,int y,int d)
{
    if(ma[x][y]=='D')
    {
        if(d==t)
        {
            ans=true;
        }
        return;
    }
    if(abs(a-x)+abs(b-y)>t-d)
    {
        return;
    }
    if((abs(a-x)+abs(b-y))%2!=(t-d)%2)
    {
        return;
    }
    if(x>0)
    {
        if(ma[x-1][y]!='H'&&!vis[x-1][y])
        {
            vis[x-1][y]=true;
            dfs(x-1,y,d+1);
            vis[x-1][y]=false;
        }
    }
    if(x<n-1)
    {
        if(ma[x+1][y]!='H'&&!vis[x+1][y])
        {
            vis[x+1][y]=true;
            dfs(x+1,y,d+1);
            vis[x+1][y]=false;
        }
    }
    if(y>0)
    {
        if(ma[x][y-1]!='H'&&!vis[x][y-1])
        {
            vis[x][y-1]=true;
            dfs(x,y-1,d+1);
            vis[x][y-1]=false;
        }
    }
    if(y<m-1)
    {
        if(ma[x][y+1]!='H'&&!vis[x][y+1])
        {
            vis[x][y+1]=true;
            dfs(x,y+1,d+1);
            vis[x][y+1]=false;
        }
    }
}

int main()
{
    int i,j;
    while(true)
    {
        cin>>n>>m>>t;
        if(n==0&&m==0)
        {
            break;
        }
        fflush(stdin);
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                cin>>ma[i][j];
                if(ma[i][j]=='D')
                {
                    a=i;
                    b=j;
                }
            }
        }
        ans=false;
        memset(vis,0,sizeof(vis));
        dfs(0,0,0);
        if(ans)
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }
    }
    return 0;
}

0

308454 LV 10 @ 2015-10-18 15:37:44

坑啊
千万要注意：
1不能经过走过的点，但是出发之后可以回到起点
2千万不要在输入数据中找S，萌萌的家就在左上角，找S 10分

0

baige123 LV 10 @ 2014-09-09 21:19:48

对于时间的奇偶性一定要注意剪枝否则TLE

0

林小雅 LV 10 @ 2010-04-15 12:57:01

顺序+搜到30次终点就直接判定No+Edogawa Conan=秒杀..

0

せ孤魂斩せ LV 8 @ 2009-11-09 18:32:32

囧遇上了Evolution SmdCn

编译通过...

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

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

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

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

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

├ 测试数据 06：答案正确... 400ms

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

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

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

├ 测试数据 10：答案正确... 9ms

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

Accepted 有效得分：100 有效耗时：528ms

0

brace_123 LV 9 @ 2009-10-27 20:27:48

留名待鄙

0

香蕉派 LV 9 @ 2009-10-26 12:20:31

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

J. Wallace LV 6 @ 2009-10-25 10:33:20

编译通过...

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

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

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

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

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

├ 测试数据 06：答案正确... 541ms

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

├ 测试数据 08：答案正确... 478ms

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

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

Unaccepted 有效得分：80 有效耗时：1019ms

编译通过...

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

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

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

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

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

├ 测试数据 06：答案正确... 509ms

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

├ 测试数据 08：答案正确... 416ms

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

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

Unaccepted 有效得分：80 有效耗时：925ms

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

。。。。。。。。。。天啊。。。败在顺序上。。

饮恨。。。。楼下的楼下，虽然我知道你好心，但是，但是。。。误人子弟啊

我觉得之所以先向左向上搜是因为没到目的地前左和上的路一般都走过了，去搜不会花多少时间，如果过了目的地，一般就在现在的位置的左上方向。。。

总之，就是这样。

我血和泪的教训告诉大家要先搜左和上的方向

0

laz LV 10 @ 2009-10-21 12:09:20

编译通过...

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

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

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

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

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

├ 测试数据 06：答案正确... 556ms

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

├ 测试数据 08：答案正确... 197ms

├ 测试数据 09：答案正确... 197ms

├ 测试数据 10：答案正确... 619ms

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

Accepted 有效得分：100 有效耗时：1569ms

...终于遇到Conan了。。=.=

遇见sunny优化半天80分。。。。

0

SecretAgent LV 10 @ 2009-10-15 17:38:21

说几个比较重要的剪枝

1.奇偶关系，如果时间和距离不是同奇同偶，那么永远无法

在规定的时间到达，直接输出no

2.最优性，如果已经走的时间，

加上到D点的最短距离超过了time那么肯定到不了。

如果还没到时间就已经搜到了D点，那么显然也不需要继续搜。

3.方向顺序，注意到起点是在左上方，所以优先向右边和下边扩展。

剪枝都加上后终于AC了，虽然耗时还是不少。

楼下给出的方向顺序很奇怪，为什么优先向左上方扩展？

难道只是针对数据？

编译通过...

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

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

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

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

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

├ 测试数据 06：答案正确... 244ms

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

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

├ 测试数据 09：答案正确... 525ms

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

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

Accepted 有效得分：100 有效耗时：1506ms

0

start_pop LV 9 @ 2009-10-12 12:18:01

大牛们为什么会超时?

var x,y,i,j,n,m,k,l,o,p,time:longint;

a:array[1..8,1..8] of char;

b:array[1..8,1..8] of boolean;

t,d:boolean;

procedure try(q,w,e:longint);

begin

if (qn)or(wm) then exit;

if (q=x)and(w=y)and(e=time) then begin t:=true;exit;end;

if e>=time then exit;

if (a[q+1,w]='*')and(b[q+1,w]=false) then begin b[q+1,w]:=true;try(q+1,w,e+1);b[q+1,w]:=false;end;

if (a[q-1,w]='*')and(b[q-1,w]=false) then begin b[q-1,w]:=true;try(q-1,w,e+1);b[q-1,w]:=false;end;

if (a[q,w+1]='*')and(b[q,w+1]=false) then begin b[q,w+1]:=true;try(q,w+1,e+1);b[q,w+1]:=false;end;

if (a[q,w-1]='*')and(b[q,w-1]=false) then begin b[q,w-1]:=true;try(q,w-1,e+1);b[q,w-1]:=false;end;

end;

begin

readln(n,m,time);

while n0 do

begin

if n=0 then halt;

t:=false;

d:=true;

for i:=1 to n do

begin

for j:=1 to m do

begin

read(a);

b:=false;

if a='S' then a:='*';

if a='D' then begin x:=i;y:=j;a:='*';end;

end;

readln;

end;

p:=x+y;

if (p mod 2)(time mod 2) then d:=false;

if d then try(1,1,0);

if t then writeln('Yes')

else writeln('No');

readln(n,m,time);

end;

end.

0

1oVe YoU疾风 LV 10 @ 2009-10-09 12:04:16

大家可以用以下方法来骗骗骗骗骗骗骗骗骗骗骗骗骗骗分啊

1.顺序搜索(lx都说过了,有点多嘴哈,不过我可没用)

2.当time > *的总数就 writeln('No');

3.设一个计数器C,每次找到'D'都inc(C) 你可以设一个顶值,当C=它的时候就EXIT; (在尝试中C最小为30左右,大到100000左右都可以)

PS.其实C剪掉了大量的冗余,当我测试时(没有加C),C竟然累加到了1000000~ ~,这让我想到可以通过限定DFS找到目标的层数来提高时间效率

附DFS 过程

procedure dfs(x,y,dep : longint);

var i , tx , ty : longint;

begin

if flag then exit;

if c = LIMIT then exit;

if dep > time then exit;

if a[x,y] = 'D' then

begin

inc(c);

if time = dep then flag := true; exit;

end;

for i := 1 to 4 do

begin

tx := x + dx[i]; ty := y + dy[i];

if (tx 0) and (ty 0) then

if (a[tx,ty] 'H') and (not v[tx,ty]) then

begin

v[tx,ty] := true;

dfs(tx,ty,dep+1);

v[tx,ty] := false;

end;

end;

end;

三星纪念!!!

0

wzc1995 LV 10 @ 2009-10-08 14:30:59

强烈建议搜索顺序用

int d[4][2]={{-1,0},{0,-1},{1,0},{0,1}};

否则超时

0

zzdx4 LV 8 @ 2009-10-06 10:04:07

DP+掐时（土法）

RP好就AC！！！

以后要好好学习概率论，

争取更多AC机会。。。

0

xiaobaibai LV 9 @ 2009-10-05 21:38:29

我X，我要喷血了。

题目没说“S”是什么，结果看成是出发点。

216了将近3H，大家引以为戒。

题目其实很简单，用奇偶剪+长度剪就行了。

水题。

0

honghaijie LV 9 @ 2009-10-05 21:20:18

考试时裸搜 60分

原来顺序能起这么大作用

没改顺序之前之前

编译通过...

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

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

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

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

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

├ 测试数据 06：答案正确... 306ms

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

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

├ 测试数据 09：答案正确... 588ms

├ 测试数据 10：答案正确... 572ms

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

Accepted 有效得分：100 有效耗时：1678ms

改了后..

编译通过...

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

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

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

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

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

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

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

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

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

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

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

Accepted 有效得分：100 有效耗时：9ms

我[color=white终于

0

li_ LV 7 @ 2009-10-04 20:48:49

编译通过...

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

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

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

├ 测试数据 04：答案错误...程序输出比正确答案长

├ 测试数据 05：答案错误...程序输出比正确答案长

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

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

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

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

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

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

Unaccepted 有效得分：80 有效耗时：0ms

var

n,m,t,i,j,tt,x,y:longint;

f:array[0..51,0..8,0..8] of boolean;

c:array[0..8,0..8] of char;

found:boolean;

begin

readln(n,m,tt);

while (n+m+tt)>0 do begin

fillchar(c,sizeof(c),0);

for i:=1 to n do begin

for j:=1 to m do begin

read(c);

if c='D' then begin

x:=i;

y:=j;

end;

end;

readln();

end;

if (x+y)and 1tt and 1 then begin

writeln('No');

readln(n,m,tt);

continue;

end;

fillchar(f,sizeof(f),false);

f[0,1,1]:=true;

found:=false;

for t:=1 to tt do

for i:=1 to n do

for j:=1 to m do

if c'H' then begin

f[t,i,j]:=f[t-1,i,j-1]or f[t-1,i-1,j]or f[t-1,i,j+1]or f[t-1,i+1,j];

if not f[t,i,j] then continue;

if c='D' then

if t=tt then found:=true

else f[t,i,j]:=false;

end;

if found then writeln('Yes') else writeln('No');

readln(n,m,tt);

end;

end.

总是80，怎么回事？？？

题解

60 条题解

萌萌赶考

信息

状态

开发

支持

题解

60 条题解

萌萌赶考

信息

状态

开发

支持

还没有账户？

登录