题解

73 条题解

  • 1
    @ 2017-08-01 15:25:53
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iomanip>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <limits>
    #include <string>
    #include <sstream>
    using namespace std;
    
    const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
    
    int n,m,t,x,y,s_i,s_j,m_i,m_j;
    int d[25+1][25+1];
    int v[25+1][25+1];
    deque<int> q_i;
    deque<int> q_j;
    char a[25+1][25+1];
    
    int main()
    {
        while (~scanf("%d%d%d",&t,&x,&y))
        {
            m=x,n=y;
            for (int i=1;i<=n;i++)
            {
                char c;
                scanf("%c",&c);
                for (int j=1;j<=m;j++)
                {
                    scanf("%c",&a[i][j]);
                    if (a[i][j]=='s')
                        a[i][j]='.',s_i=i,s_j=j;
                    else if (a[i][j]=='m')
                        a[i][j]='.',m_i=i,m_j=j;
                }
            }
            int mov_i[4]={-1,0,0,1};
            int mov_j[4]={0,-1,1,0};
            memset(d,oo_max,sizeof(d));
            memset(v,0,sizeof(v));
            for (d[s_i][s_j]=0,v[s_i][s_j]=1,q_i.resize(0),q_j.resize(0),q_i.push_back(s_i),q_j.push_back(s_j);(!q_i.empty())&&(!q_j.empty());v[q_i.front()][q_j.front()]=0,q_i.pop_front(),q_j.pop_front())
            {
                int now_i=q_i.front(),now_j=q_j.front();
                for (int i=0;i<4;i++)
                {
                    int next_i=now_i+mov_i[i],next_j=now_j+mov_j[i];
                    if (1<=next_i&&next_i<=n&&1<=next_j&&next_j<=m&&a[next_i][next_j]!='o'&&d[now_i][now_j]+((a[next_i][next_j]=='#')?2:1)<d[next_i][next_j])
                    {
                        d[next_i][next_j]=d[now_i][now_j]+((a[next_i][next_j]=='#')?2:1);
                        if (v[next_i][next_j]==0)
                            v[next_i][next_j]=1,q_i.push_back(next_i),q_j.push_back(next_j);
                    }
                }
            }
            printf("%d\n",((d[m_i][m_j]<t)?d[m_i][m_j]:55555));
        }
    }
    
  • 0
    @ 2015-08-16 17:06:38

    最短路径,去屎吧!
    BFS秒杀!
    因为这个图中权值只有1和2两种可能,所以我们在搜到所有权值是2的点的时候在队列里面打一个标记,表示这个格子走的比较慢,等一轮才能扩展子节点。如果当前节点有个标记,那就把它直接出队,再入队,但是消掉它的标记。因为这个节点再入队以后的位置正好是当前的节点的子节点的位置,所以到达的时间都比这一段到达时间多1。因为这个有标记的节点在被检查到的时候,这个节点附近的节点时间是这个节点的前驱被扩展到的时间+1,所以这样放回队尾一次以后,它被处理的时间是他被发现的时间+2,正好是草地的通过时间。其实对于权值随意的图,也可以用这个方法,但是标记用一个正整数来表示它还要放回队尾的次数,被发现的时候就是发现它的节点的边权。这个方法的时间复杂度是O(最大边权*(V+E)),这个图里面最大边权固定,所以是O(V+E)。这个方法在权是整数,并且普遍很小的时候有用。

    program P1340;
    type
    tLoc=record
    x,y,flag:integer;
    end;
    const
    toward:array[1..4,1..2] of integer=((0,1),(0,-1),(1,0),(-1,0));
    var
    queue:array[1..10000] of tLoc;
    top,tail:integer;
    map:array[1..25,1..25] of char;
    time:array[1..25,1..25] of integer;
    height,length,melt:integer;
    i,j:integer;
    a,b:integer;
    begin
    readln(melt);
    readln(length);
    readln(height);
    for i:=1 to height do
    begin
    for j:=1 to length do
    begin
    read(map[i,j]);
    if map[i,j]='s' then
    begin
    time[i,j]:=0;
    a:=i;
    b:=j;
    end
    else
    begin
    time[i,j]:=-1;
    end;
    end;
    readln;
    end;
    top:=2;
    tail:=1;
    queue[1].x:=a;
    queue[1].y:=b;
    queue[1].flag:=0;
    while (top>tail) and (map[queue[tail].x,queue[tail].y]<>'m') do
    begin
    with queue[tail] do
    begin
    if flag>0 then
    begin
    queue[top].flag:=0;
    queue[top].x:=x;
    queue[top].y:=y;
    inc(top);
    inc(tail);
    continue;
    end;
    for i:=1 to 4 do
    begin
    if ((x+toward[i,1]>=1) and (x+toward[i,1]<=height))and((y+toward[i,2]>=1) and (y+toward[i,2]<=length)) then
    begin
    if (time[x+toward[i,1],y+toward[i,2]]=-1) and (map[x+toward[i,1],y+toward[i,2]]<>'o') then
    begin
    queue[top].x:=x+toward[i,1];
    queue[top].y:=y+toward[i,2];
    if map[x+toward[i,1],y+toward[i,2]]='#' then
    begin
    queue[top].flag:=1;
    end
    else
    begin
    queue[top].flag:=0;
    end;
    if map[x,y]='#' then
    begin
    time[x+toward[i,1],y+toward[i,2]]:=time[x,y]+2;

    end
    else
    begin
    time[x+toward[i,1],y+toward[i,2]]:=time[x,y]+1;
    end;
    inc(top);
    end;
    end;
    end;
    end;
    inc(tail);
    end;
    if map[queue[tail].x,queue[tail].y]<>'m' then
    begin
    writeln('55555');
    end
    else
    begin
    if time[queue[tail].x,queue[tail].y]>=melt then
    begin
    writeln('55555');
    end
    else
    begin
    writeln(time[queue[tail].x,queue[tail].y]);
    end;
    end;
    end.

  • 0
    @ 2015-02-02 14:14:00

    SPFA大爱
    构图别写错了....

    Code

    const int INF=(1<<28)-1;

    struct edge
    {
    int in;
    edge*nxt;
    }pool[8000];
    edge*et=pool;
    edge*eds[1000];
    void addedge(int a,int b)
    { et->in=b; et->nxt=eds[a]; eds[a]=et++; }
    #define FOREACH_EDGE(i,j) for(edge*i=eds[j];i;i=i->nxt)

    int n;

    char M[1000];
    int d[1000];

    int st,ed;
    int dist[1000];
    int qh,qt;
    int q[2000000];
    int SPFA()
    {
    fillarray(dist,INF,n);

    qh=qt=0;
    q[qt++]=st;
    dist[st]=0;
    d[st]=0;
    d[ed]=1;
    while(qh!=qt)
    {
    int&cur=q[qh];
    FOREACH_EDGE(i,cur)
    if( M[i->in]!='o' && dist[i->in] > dist[cur] + d[i->in])
    {
    dist[i->in]=dist[cur]+d[i->in];
    q[qt++]=i->in;
    }
    qh++;
    }

    return dist[ed];
    }

    #define POINT(i,j) (((i)*yl)+(j))
    int tlim;
    int xl,yl;

    int main()
    {
    tlim=getint();
    yl=getint();
    xl=getint();
    n=xl*yl;

    for(int i=0;i<xl;i++)
    scanf("%s",M+i*yl);

    for(int i=0;i<xl;i++)
    for(int j=0;j<yl;j++)
    {
    if(i>0) addedge(POINT(i,j),POINT(i-1,j));
    if(j>0) addedge(POINT(i,j),POINT(i,j-1));
    if(i<xl-1) addedge(POINT(i,j),POINT(i+1,j));
    if(j<yl-1) addedge(POINT(i,j),POINT(i,j+1));

    if(M[POINT(i,j)]=='m') st=POINT(i,j);
    if(M[POINT(i,j)]=='s') ed=POINT(i,j);
    if(M[POINT(i,j)]=='.') d[POINT(i,j)]=1;
    if(M[POINT(i,j)]=='#') d[POINT(i,j)]=2;
    }

    int res=SPFA();

    if(tlim<=res) printf("55555\n");
    else printf("%d\n",res);

    return 0;
    }

  • 0
    @ 2012-10-19 10:15:10

    本来以为是dfs,就用dfs的思路写了,结果写出来竟然发现莫名其妙的写了个广搜。。rp++了~

  • 0
    @ 2012-07-17 16:33:11

    在bfs中

    要特判一种情况,走草地时如果直接将步数+2,程序可能会提前标记所走过的位置,

    注意是"提前",

    所以可能不会算出最优解

    如果大家有犯这个错误,可以来看一下

  • 0
    @ 2009-11-09 21:57:12

    BFS 不用判重 运算结束出解

    要注意的是 '#'情况可能被后面的'.'所替代

    Const

    dx:array[1..4] of longint=(1,-1,0,0);

    dy:array[1..4] of longint=(0,0,1,-1);

    Var

    mx,my,z,head,tail,n,x,y,i,j:longint;

    g:array[1..25,1..25] of char;

    f:array[0..62500,1..2] of longint;

    h:array[1..25,1..25] of longint;

    function pp(a,b:longint):boolean;

    begin

    if (a>0) and (a0) and (btail then inc(tail);

    f[t,1]:=f[x,1]+dx[i];

    f[t,2]:=f[x,2]+dy[i];

    h[f[t,1],f[t,2]]:=h[f[x,1],f[x,2]]+k;

    end;

    end;

    end;

    end;

    begin

    LL_F(x);

    while headtail do

    begin

    inc(head);

    LL_F(head);

    end;

    end;

    begin

    readln(n);

    readln(y);

    readln(x);

    z:=x*y;

    for i:=1 to x do

    begin

    for j:=1 to y do

    begin

    read(g);

    if g='s' then

    begin f[1,1]:=i;f[1,2]:=j; g:='o';end else

    if g='m' then

    begin mx:=i;my:=j; end;

    end;

    readln;

    end;

    head:=1;tail:=1;

    L_F(1);

    wri(h[mx,my]);

    end.

  • 0
    @ 2009-11-03 23:21:07

    编译通过...

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

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

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

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

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

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

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

    var t,m,n,i,j,min:longint;

    a:array[0..26,0..27]of char;

    used:array[0..26,0..26]of boolean;

    dx:array[1..4]of integer=(1,0,-1,0);

    dy:array[1..4]of integer=(0,1,0,-1);

    f:array[0..26,0..26]of longint;

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

    var i:longint;

    begin

    if dep>=t then exit;

    if (a[x,y]='m') then

    begin

    if depdep+1) then

    begin

    used[x+dx[i],y+dy[i]]:=true;

    f[x+dx[i],y+dy[i]]:=dep+1;

    find(dep+1,x+dx[i],y+dy[i]);

    used[x+dx[i],y+dy[i]]:=false;

    end

    else if (a[x+dx[i],y+dy[i]]='#')and(f[x+dx[i],y+dy[i]]>dep+2) then

    begin

    used[x+dx[i],y+dy[i]]:=true;

    f[x+dx[i],y+dy[i]]:=dep+2;

    find(dep+2,x+dx[i],y+dy[i]);

    used[x+dx[i],y+dy[i]]:=false;

    end

    end;

    end;

    begin

    readln(t);

    readln(m);

    readln(n);

    for i:=0 to n+1 do

    for j:=0 to m+1 do

    begin

    used:=true;

    f:=99999999;

    end;

    for i:=1 to n do

    begin

    for j:=1 to m do

    begin

    read(a);

    used:=false;

    end;

    readln;

    end;

    min:=99999999;

    for i:=1 to n do

    for j:=1 to m do

    if a='s' then

    begin

    used:=true;

    find(0,i,j);

    if min=99999999 then writeln(55555)

    else writeln(min);

    halt;

    end;

    end.

    DFS.本只得20分.但看楼下题解优化后便秒杀

  • 0
    @ 2009-10-30 14:57:00

    直接BFS

  • 0
    @ 2009-10-30 14:03:31

    小弟不才果然牛逼;

    膜拜神牛;

    这都ac了;

    ~~~~

    水啊水啊

  • 0
    @ 2009-10-30 14:02:06

    小弟果然不才,水题做了好久。

    bfs enough,简单搜,别搞复杂的,小弟做人就追求简单

    不说了,电脑流水了

    编译通过...

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

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

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

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

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

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

    Accepted 有效得分:100 有效耗时:0ms const d1:array[1..4] of integer=(0,1,0,-1);

    d2:array[1..4] of integer=(1,0,-1,0);

    type date=record

    m,n,c:integer;

    end;

    var map:array[0..26,0..26] of integer;

    i,j,ans,x,y,q1,q2,t:integer;

    q:array[0..700] of date;

    procedure init;

    var i,j:integer;

    ch:char;

    begin readln(x,y);

    for i:=0 to 26 do

    for j:= 0 to 26 do

    map:=0;

    for i:=1 to y do

    begin for j:=1 to x do

    begin read(ch);

    if (ch='s') or ( ch='S') then begin q1:=i;q2:=j; end;

    if (ch='m') then map:=3;

    if ch='.' then map:=1;

    if ch='#' then map:=2;

    end;

    readln;

    end;

    end;

    procedure bfs;

    var top,rear,i:integer;

    flag:boolean;

    begin top:=1; rear:=1; q[1].m:=q1; q[1].n:=q2; q[1].c:=0; flag:=false;

    while top=1) and(q[top].m+d1[i]=1) and (q[top].n+d2[i]=1) and(q[top].m+d1[i]=1) and (q[top].n+d2[i]

  • 0
    @ 2009-10-26 19:30:57

    把地图转换成一张无向图,

    对于道路和起点,出度为1

    对于草地,出度为2

    对于障碍和终点,出度为无限大

    接下来求一次单源最短路即可

    编译通过...

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

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

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

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

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

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

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

  • 0
    @ 2009-10-18 19:54:22

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

    就是BFS.....

    第一次令人诧异的80分,加了个“=”秒杀....

    一定要注意刚好融化.....

  • 0
    @ 2009-10-14 19:31:14

    编译通过...

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

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

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

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

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

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

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

    BFS...裸的

  • 0
    @ 2009-09-03 20:53:05

    用SPFA一次AC

  • 0
    @ 2009-09-02 18:34:53

    BFS秒杀 O(∩_∩)O

    可惜没一次ac……

    “判断按照最优方案是否可以赶在冰淇淋融化之前到达冰淇淋店(注:当T=最优方案所用时间,则判断为未赶到),如赶到,输出所用时间;如未赶到,输出Tina的哭声——“55555”(不包括引号)。”

    审题能力有待提高……

  • 0
    @ 2009-08-10 19:52:03

    DFS交了三次,裸搜第3,5点会超时。多亏了340508965神牛的帮助,才过的。

    用f[x,y]记录到达[x,y]的最小时间如果超过就忽律此点,不用继续了。

  • 0
    @ 2009-07-23 20:01:22

    数据好弱,很普通的BFS就秒了,可惜没加等号unac了几次

    const

    dx:array[1..4]of longint=(-1,0,1,0);

    dy:array[1..4]of longint=(0,1,0,-1);

    type

    sate=record

    x,y:longint;

    special:boolean;

    step:longint;

    pre:longint;

    end;

    var

    temp:string;

    min,t,tm,x,y,i,j,k,head,tail,x1,y1,l,r:longint;

    a:array[1..100000]of sate;

    m:array[1..25,1..25]of char;

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

    c:array[1..100]of longint;

    begin

    tm:=0;

    fillchar(b,sizeof(b),true);

    readln(t);

    readln(x);

    readln(y);

    for i:=1 to y do

    begin

    readln(temp);

    for j:=1 to x do

    begin

    m[j,i]:=temp[j];

    if m[j,i]='s' then

    begin

    x1:=j;

    y1:=i;

    end;

    end;

    end;

    b[x1,y1]:=false;

    a[1].x:=x1;

    a[1].y:=y1;

    a[1].step:=0;

    a[1].special:=false;

    a[1].pre:=0;

    head:=0;

    tail:=1;

    repeat

    inc(head);

    if a[head].special then

    begin

    inc(tail);

    a[tail].x:=a[head].x;

    a[tail].y:=a[head].y;

    a[tail].step:=a[head].step+1;

    a[tail].special:=false;

    a[tail].pre:=a[head].pre;

    end

    else

    for i:=1 to 4 do

    begin

    l:=dx[i]+a[head].x;

    r:=dy[i]+a[head].y;

    if(l>0)and(r>0)and(l

  • 0
    @ 2009-07-17 15:49:34

    嘢 一次秒杀

    编译通过...

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

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

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

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

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

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

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

    话说 暴力永远是解决问题的好办法啊啊哈O(∩_∩)O哈!

    就是不知道我这个带着有点儿记忆化的搜索算不算暴力啊

    program p1340;

    var n,m,t,i,j,x0,y0,xi,yi:longint;

    ch:char;

    a:array[1..4,0..1] of integer;

    f,tim:array[0..30,0..30] of longint;

    procedure search(xt,yt:longint);

    var r:longint;

    begin

    if (xt=xi)and(yt=yi) then exit

    else

    for r:=1 to 4 do

    if f[xt,yt]+tim[xt+a[r,0],yt+a[r,1]]f[xi,yi] then writeln(f[xi,yi])

    else writeln(55555);

    end.

  • 0
    @ 2009-06-02 12:41:02

    编译通过...

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

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

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

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

    ├ 测试数据 05:答案错误... ├ 标准行输出 70

     ├ 错误行输出 23

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

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

    为什么会这样??

  • 0
    @ 2009-05-23 18:01:06

    可以用spfa做,注意第四个点。

    所用时间必须严格小于规定时间才输出最小时间。

信息

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