1 条题解
-
0
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
- 上传者