1 条题解

  • 0
    @ 2021-6-15 10:09:47

    C++ :

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #define rep(i,n) for(int i=0;i<n;i++)
    using namespace std;
    const int N = 30, INF = 0x7f7f7f7f, dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
    int mp[N*N];
    int n, m, p, ex, ey, sx, sy, tx, ty;
    bool inq[N*N][4];
    int Dist[N*N][4], d[N*N], dis[N*N][4][4];
    typedef pair<int, int> pii;
    queue<pii>Q;
    queue<int>q;
    
    int path(int es, int ts, int ss) {
        memset(d, -1, sizeof(d));
        while(!q.empty())q.pop();
        q.push(es);
        d[es] = 0;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            if(u == ts)return d[u];
            int x = u / m, y = u % m;
            rep(i, 4) {
                int nx = x + dir[i][0], ny = y + dir[i][1];
                if(nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
                int ns = nx * m + ny;
                if(!mp[ns] || d[ns] != -1 || ns == ss)continue;
                d[ns] = d[u] + 1;
                q.push(ns);
            }
        }
        return -1;
    }
    
    void init(int r, int c) {
        if(!mp[r * m + c])return;
        for(int i = 0; i < 4; i++)
            for(int j = i + 1; j < 4; j++) {
                int ix = r + dir[i][0], iy = c + dir[i][1];
                if(ix < 0 || ix >= n || iy < 0 || iy >= m || !mp[ix*m+iy])continue;
                int jx = r + dir[j][0], jy = c + dir[j][1];
                if(jx < 0 || jx >= n || jy < 0 || jy >= m || !mp[jx*m+jy])continue;
                dis[r * m + c][i][j] = dis[r * m + c][j][i] = path(ix * m + iy, jx * m + jy, r * m + c);
            }
    }
    
    int work() {
        scanf("%d%d%d%d%d%d", &ex, &ey, &sx, &sy, &tx, &ty);
        ex--;
        ey--;
        sx--;
        sy--;
        tx--;
        ty--;
        if(sx == tx && sy == ty)return 0;
        memset(Dist, 0x7f, sizeof(Dist));
        int ss = sx * m + sy;
        rep(i, 4) {
            int nx = sx + dir[i][0], ny = sy + dir[i][1];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
            int dist = path(ex * m + ey, nx * m + ny, ss);
            if(dist == -1)continue;
            Dist[ss][i] = dist;
            Q.push(make_pair(ss, i));
            inq[ss][i] = true;
        }
        while(!Q.empty()) {
            pii u = Q.front();
            Q.pop();
            int k = u.first, s = u.second;
            int x = k / m, y = k % m;
            inq[x * m + y][s] = false;
            int px = x + dir[s][0], py = y + dir[s][1];
            if(Dist[px * m + py][s ^ 1] > Dist[x * m + y][s] + 1) {
                Dist[px * m + py][s ^ 1] = Dist[x * m + y][s] + 1;
                if(inq[px * m + py][s ^ 1])continue;
                Q.push(make_pair(px * m + py, s ^ 1));
                inq[px * m + py][s ^ 1] = true;
            }
            rep(i, 4) {
                if(i == s)continue;
                int dist = dis[x * m + y][s][i];
                if(dist == -1)continue;
                if(Dist[x * m + y][i] > Dist[x * m + y][s] + dist) {
                    Dist[x * m + y][i] = Dist[x * m + y][s] + dist;
                    if(inq[x * m + y][i])continue;
                    Q.push(make_pair(x * m + y, i));
                    inq[x * m + y][i] = true;
                }
            }
        }
        int ans = INF;
        rep(i, 4)ans = min(ans, Dist[tx * m + ty][i]);
        if(ans == INF)return -1;
        return ans;
    }
    
    int main() {
        while(~scanf("%d%d%d", &n, &m, &p)) {
            rep(i, n)rep(j, m)scanf("%d", &mp[i * m + j]);
            memset(dis, -1, sizeof(dis));
            rep(i, n)rep(j, m)init(i, j);
            rep(i, p)printf("%d\n", work());
        }
        return 0;
    }
    

    Pascal :

    program puzzle;{day2t3}
    const dx:array[1..4]of -1..1=(0,1,-1,0);
          dy:array[1..4]of -1..1=(1,0,0,-1); 
    type edgenode=^edge;
          edge=record
           dir,w:longint;
           next:edgenode;
          end; 
    var v1,map:array[0..31,0..31]of boolean;
        a:array[1..30,1..30,1..4]of edgenode;
        d1:array[1..30,1..30]of longint;
        d2:array[1..30,1..30,1..4]of longint;
        q1:array[1..10000,1..2]of integer;
        q2:array[1..100000,1..3]of longint;
        v2:array[1..30,1..30,1..4]of boolean;
        ans,f,r,ex,ey,sx,sy,tx,ty,n,m,q,i,j,k,l:longint;
        c:edgenode;
    procedure bfs(s1,s2,t1,t2:integer);
    var r,f,i,p,q:longint;
     begin
     fillchar(d1,sizeof(d1),255); {统计距离,填充为-1}
     fillchar(v1,sizeof(v1),0); {访问标记}
     fillchar(q1,sizeof(q1),0); {队列}
     f:=0; r:=1; q1[1,1]:=s1; q1[1,2]:=s2; d1[s1,s2]:=0; v1[s1,s2]:=true; {}
     while f<r do
      begin
      inc(f); p:=q1[f,1]; q:=q1[f,2]; {取出队列中的头结点}
      for i:=1 to 4 do
       if (map[p+dx[i],q+dy[i]])and(d1[p+dx[i],q+dy[i]]=-1)
       then
        begin
        d1[p+dx[i],q+dy[i]]:=d1[p,q]+1; {距离+1}
        if (p+dx[i]=t1)and(q+dy[i]=t2) then exit; {到达目标节点,退出}
        if not v1[p+dx[i],q+dy[i]]
        then
         begin
         inc(r); q1[r,1]:=p+dx[i]; q1[r,2]:=q+dy[i]; v1[p+dx[i],q+dy[i]]:=true;
         end;
        end;
      v1[p,q]:=false;
      end;
     end; 
    {++++main++++} 
    begin
     readln(n,m,q);
     for i:=1 to n do
      for j:=1 to m do
       begin
       read(k);
       if k=1 then map[i,j]:=true; {可以移动的棋子或空格}
       end;
     for i:=1 to n do
      for j:=1 to m do
       if map[i,j]
       then
        for k:=1 to 4 do
         if map[i+dx[k],j+dy[k]]
         then
          begin
          map[i,j]:=false;
          for l:=1 to 4 do
           if (k<>l)and(map[i+dx[l],j+dy[l]])
           then
            begin
            bfs(i+dx[k],j+dy[k],i+dx[l],j+dy[l]);
            if d1[i+dx[l],j+dy[l]]<>-1
            then 
             begin
             new(c); c^.dir:=l; c^.w:=d1[i+dx[l],j+dy[l]]; c^.next:=a[i,j,k]; a[i,j,k]:=c;
             end;
            end;
          map[i,j]:=true;
          end;
     for i:=1 to q do
      begin
      fillchar(q2,sizeof(q2),0);
      fillchar(d2,sizeof(d2),255);
      fillchar(v2,sizeof(v2),0); f:=0; r:=0;
      readln(ex,ey,sx,sy,tx,ty);
      if ((ex=sx)and(ey=sy))or((ex=0)or(ey=0))
      then begin writeln(-1); continue; end;
      if(sx=tx)and(sy=ty)
      then begin writeln(0); continue; end;
      map[sx,sy]:=false;
      for j:=1 to 4 do
       if map[sx+dx[j],sy+dy[j]]
       then
        begin
        bfs(ex,ey,sx+dx[j],sy+dy[j]);
        if d1[sx+dx[j],sy+dy[j]]<>-1
        then
         begin
         inc(r);
         q2[r,1]:=sx; q2[r,2]:=sy; q2[r,3]:=j;
         d2[sx,sy,j]:=d1[sx+dx[j],sy+dy[j]];
         v2[sx,sy,j]:=true;
         end;
        end; 
      map[sx,sy]:=true;
      while f<r do
       begin
       inc(f);
       c:=a[q2[f,1],q2[f,2],q2[f,3]];
       while c<>nil do
        begin
        if (d2[q2[f,1],q2[f,2],c^.dir]=-1)
            or(d2[q2[f,1],q2[f,2],c^.dir]>d2[q2[f,1],q2[f,2],q2[f,3]]+c^.w)
        then
         begin
         d2[q2[f,1],q2[f,2],c^.dir]:=d2[q2[f,1],q2[f,2],q2[f,3]]+c^.w;
         if not v2[q2[f,1],q2[f,2],c^.dir]
         then 
          begin
          inc(r); q2[r,1]:=q2[f,1]; q2[r,2]:=q2[f,2]; q2[r,3]:=c^.dir;
          v2[q2[f,1],q2[f,2],c^.dir]:=true;
          end;
         end;
        c:=c^.next;
        end;
       if (d2[q2[f,1]+dx[q2[f,3]],q2[f,2]+dy[q2[f,3]],5-q2[f,3]]=-1)
          or(d2[q2[f,1]+dx[q2[f,3]],q2[f,2]+dy[q2[f,3]],5-q2[f,3]]>d2[q2[f,1],q2[f,2],q2[f,3]]+1)
       then
        begin
        d2[q2[f,1]+dx[q2[f,3]],q2[f,2]+dy[q2[f,3]],5-q2[f,3]]:=d2[q2[f,1],q2[f,2],q2[f,3]]+1;
        if not v2[q2[f,1]+dx[q2[f,3]],q2[f,2]+dy[q2[f,3]],5-q2[f,3]]
        then
         begin
         inc(r); q2[r,1]:=q2[f,1]+dx[q2[f,3]]; q2[r,2]:=q2[f,2]+dy[q2[f,3]];q2[r,3]:=5-q2[f,3];
         v2[q2[f,1]+dx[q2[f,3]],q2[f,2]+dy[q2[f,3]],5-q2[f,3]]:=true;
         end;
        end;
       v2[q2[f,1],q2[f,2],q2[f,3]]:=false;
       end;
      ans:=maxlongint;
      for j:=1 to 4 do
       if (d2[tx,ty,j]<>-1)and(d2[tx,ty,j]<ans)
       then ans:=d2[tx,ty,j];
      if ans=maxlongint
      then writeln(-1) else writeln(ans);
      end;
    end. 
    
    
    • 1

    信息

    ID
    320
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者