记录编号 | 193481 | 评测结果 | AAAAAAAAAAAAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | [NOIP 2013]华容道 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | C++ | 运行时间 | 0.223 s | ||
提交时间 | 2015-10-14 20:19:31 | 内存使用 | 3.96 MiB | ||
#include<cstdio> #include<iostream> #include<cmath> #include<deque> using namespace std; const int SIZEN=40,INF=0x7fffffff/2,SIZED=40*40*4; int N,M,q,tot=0; int id[SIZEN][SIZEN][4]={0}; int sw[SIZED]; bool mp[SIZEN][SIZEN]={0}; int dx[]={1,-1,0,0},dy[]={0,0,1,-1}; deque<pair<int,int> > s[SIZED]; void read() { scanf("%d%d%d",&N,&M,&q); for(int i=1;i<=N;i++)for(int j=1;j<=M;j++)scanf("%d",&mp[i][j]); for(int i=1;i<=N;i++)for(int j=1;j<=M;j++)for(int k=0;k<4;k++) id[i][j][k]=++tot; } int BFS(int xf,int yf,int xt,int yt) { int ans=INF; deque<pair<int,int> > Q; Q.push_back(make_pair(xf,yf)); int qs=Q.size(),step=0; bool inq[SIZEN][SIZEN]={0}; while(!Q.empty()) { pair<int,int> P; P=Q.front();Q.pop_front(); if(P.first==xt&&P.second==yt) {ans=step;break;} for(int i=0;i<4;i++) { int x=P.first+dx[i],y=P.second+dy[i]; if(!mp[x][y]) continue; if(!inq[x][y]) { inq[x][y]=1; Q.push_back(make_pair(x,y)); } } qs--; if(qs==0) { qs=Q.size(); step++; } if(step>N*M) break; } return ans; } void spfa() { deque<int> Q; Q.push_back(0); bool inq[SIZED]={0}; Q.push_back(0); inq[0]=1; for(int i=0;i<=tot;i++) sw[i]=INF; sw[0]=0; while(!Q.empty()) { int x=Q.front();Q.pop_front();inq[x]=0; for(int i=0;i<s[x].size();i++) { int v=s[x][i].first,w=s[x][i].second; if(sw[x]+w<sw[v]) { sw[v]=sw[x]+w; if(!inq[v]) { inq[v]=1; Q.push_back(v); } } } } } void add(int fr,int to,int l){ s[fr].push_back(make_pair(to,l));} void prepare() { for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) { if(!mp[i][j]) continue; int nx,ny; for(int k=0;k<4;k++) { nx=i+dx[k],ny=j+dy[k]; //cout<<nx<<" "<<ny<<endl; if(!mp[nx][ny]) continue; add(id[i][j][k],id[nx][ny][k^1],1); for(int e=0;e<4;e++) { if(e==k) continue; int tx=i+dx[e],ty=j+dy[e]; //cout<<nx<<" "<<ny<<" "<<tx<<" "<<ty<<endl; if(!mp[tx][ty]) continue; mp[i][j]=0; int w=BFS(nx,ny,tx,ty); if(w!=INF) add(id[i][j][k],id[i][j][e],w); mp[i][j]=1; } } } } int clac(int ex,int ey,int sx,int sy,int tx,int ty) { if(ex==sx&&ey==sy) return 0; if(!mp[ex][ey]||!mp[sx][sy]) return -1; int ans=INF; mp[sx][sy]=0; s[0].clear(); for(int i=0;i<4;i++) { int x=sx+dx[i],y=sy+dy[i]; if(!mp[x][y]) continue; int w=BFS(tx,ty,x,y); if(w<INF) add(0,id[sx][sy][i],w); } mp[sx][sy]=1; spfa(); for(int i=0;i<4;i++) ans=min(ans,sw[id[ex][ey][i]]); if(ans<INF) return ans; return -1; } void work() { int ex,ey,sx,sy,tx,ty; for(int i=1;i<=q;i++) { scanf("%d%d%d%d%d%d",&tx,&ty,&sx,&sy,&ex,&ey); printf("%d\n",clac(ex,ey,sx,sy,tx,ty)); } } int main() { freopen("PuzzleNOIP2013.in","r",stdin); freopen("PuzzleNOIP2013.out","w",stdout); read(); prepare(); work(); return 0; }