| 记录编号 |
439626 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[NOIP 2013]华容道 |
最终得分 |
100 |
| 用户昵称 |
 하루Kiev |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.899 s |
| 提交时间 |
2017-08-21 11:16:26 |
内存使用 |
6.28 MiB |
显示代码纯文本
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
#define inf 0x6fffffff
#define size 35
typedef pair<int,int>pos;
int map[size][size],dis[250005],bj[size][size],st[250005],diss[250005];
int zz1,zz,ans;
int n,m,q,ex,ey,sx,sy,tx,ty;
struct node{int to,next,w;}e[250005];
void add(int x,int y,int z){
e[++zz].to=y;
e[zz].next=st[x];
e[zz].w=z;
st[x]=zz;
}
void bfs(int x,int y,int dx,int dy,int po){
memset(dis,0,sizeof(dis));
queue<pos>q;
q.push(make_pair(x,y));
dis[bj[x][y]]=1;
while(!q.empty()){
int xx=q.front().first,yy=q.front().second;
if(xx-1>0&&(xx-1!=dx||yy!=dy)&&map[xx-1][yy]&&!dis[bj[xx-1][yy]]){
q.push(make_pair(xx-1,yy));
dis[bj[xx-1][yy]]=dis[bj[xx][yy]]+1;
}
if(xx+1<=n&&(xx+1!=dx||yy!=dy)&&map[xx+1][yy]&&!dis[bj[xx+1][yy]]){
q.push(make_pair(xx+1,yy));
dis[bj[xx+1][yy]]=dis[bj[xx][yy]]+1;
}
if(yy-1>0&&(xx!=dx||yy-1!=dy)&&map[xx][yy-1]&&!dis[bj[xx][yy-1]]){
q.push(make_pair(xx,yy-1));
dis[bj[xx][yy-1]]=dis[bj[xx][yy]]+1;
}
if(yy+1<=m&&(xx!=dx||yy+1!=dy)&&map[xx][yy+1]&&!dis[bj[xx][yy+1]]){
q.push(make_pair(xx,yy+1));
dis[bj[xx][yy+1]]=dis[bj[xx][yy]]+1;
}
q.pop();
}
add(bj[dx][dy]*100+po*3,bj[x][y]*100+(po^1)*3,1);
if((dx-1!=x||dy!=y)&&dis[bj[dx-1][dy]]){ add(bj[dx][dy]*100+po*3,bj[dx][dy]*100+0*3,dis[bj[dx-1][dy]]-1);/*cout<<po<<" "<<0<<" "<<dis[bj[dx-1][dy]]-1<<endl;*/}
if((dx+1!=x||dy!=y)&&dis[bj[dx+1][dy]]){ add(bj[dx][dy]*100+po*3,bj[dx][dy]*100+1*3,dis[bj[dx+1][dy]]-1);/*cout<<po<<" "<<1<<" "<<dis[bj[dx+1][dy]]-1<<endl;*/}
if((dx!=x||dy-1!=y)&&dis[bj[dx][dy-1]]){ add(bj[dx][dy]*100+po*3,bj[dx][dy]*100+2*3,dis[bj[dx][dy-1]]-1);/*cout<<po<<" "<<2<<" "<<dis[bj[dx][dy-1]]-1<<endl;*/}
if((dx!=x||dy+1!=y)&&dis[bj[dx][dy+1]]){ add(bj[dx][dy]*100+po*3,bj[dx][dy]*100+3*3,dis[bj[dx][dy+1]]-1);/*cout<<po<<" "<<3<<" "<<dis[bj[dx][dy+1]]-1<<endl;*/}
}
void search(int x,int y,int dx,int dy){
memset(dis,0,sizeof(dis));
queue<pos>q;
queue<int>q1;
q.push(make_pair(x,y));
q1.push(1);
dis[bj[x][y]]=1;
while(!q.empty()){
int xx=q.front().first,yy=q.front().second,step=q1.front();
if(xx-1>0&&(xx-1!=dx||yy!=dy)&&map[xx-1][yy]&&!dis[bj[xx-1][yy]]){
q.push(make_pair(xx-1,yy));
dis[bj[xx-1][yy]]=step+1;
q1.push(step+1);
}
if(xx+1<=n&&(xx+1!=dx||yy!=dy)&&map[xx+1][yy]&&!dis[bj[xx+1][yy]]){
q.push(make_pair(xx+1,yy));
dis[bj[xx+1][yy]]=step+1;
q1.push(step+1);
}
if(yy-1>0&&(xx!=dx||yy-1!=dy)&&map[xx][yy-1]&&!dis[bj[xx][yy-1]]){
q.push(make_pair(xx,yy-1));
dis[bj[xx][yy-1]]=step+1;
q1.push(step+1);
}
if(yy+1>0&&(xx!=dx||yy+1!=dy)&&map[xx][yy+1]&&!dis[bj[xx][yy+1]]){
q.push(make_pair(xx,yy+1));
dis[bj[xx][yy+1]]=step+1;
q1.push(step+1);
}
q.pop();
q1.pop();
}
}
bool flag[250005];
void spfa(int x,int y){
memset(diss,0x7f,sizeof(diss));
queue<int> q;
if(dis[bj[x-1][y]]){
q.push(bj[x][y]*100+0*3);
diss[bj[x][y]*100+0*3]=dis[bj[x-1][y]]-1;
flag[bj[x][y]*100+0*3]=1;
}
if(dis[bj[x+1][y]]){
q.push(bj[x][y]*100+1*3);
diss[bj[x][y]*100+1*3]=dis[bj[x+1][y]]-1;
flag[bj[x][y]*100+1*3]=1;
}
if(dis[bj[x][y-1]]){
q.push(bj[x][y]*100+2*3);
diss[bj[x][y]*100+2*3]=dis[bj[x][y-1]]-1;
flag[bj[x][y]*100+2*3]=1;
}
if(dis[bj[x][y+1]]){
q.push(bj[x][y]*100+3*3);
diss[bj[x][y]*100+3*3]=dis[bj[x][y+1]]-1;
flag[bj[x][y]*100+3*3]=1;
}
while(!q.empty()){
int k=q.front();
for(int i=st[k];i;i=e[i].next){
int t=e[i].to;
if(diss[t]>diss[k]+e[i].w){
diss[t]=diss[k]+e[i].w;
if(!flag[t]){
flag[t]=1;
q.push(t);
}
}
}
q.pop();
flag[k]=0;
}
}
int main(){
freopen("PuzzleNOIP2013.in","r",stdin);
freopen("PuzzleNOIP2013.out","w",stdout);
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&map[i][j]);
bj[i][j]=++zz1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(map[i][j]){//从i,j四周出发通向其他四个位置的步数，不可经过i,j
if(map[i-1][j]) bfs(i-1,j,i,j,0);//0向上
if(map[i+1][j]) bfs(i+1,j,i,j,1);//1向下
if(map[i][j-1]) bfs(i,j-1,i,j,2);//2向左
if(map[i][j+1]) bfs(i,j+1,i,j,3);//3向右
}//搜完一遍后只加边，不保存
while(q--){
scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
if(sx==tx&&sy==ty) {printf("0\n");continue;}
search(ex,ey,sx,sy);//确定从ex,ey出发最短路，不经过sx,sy
spfa(sx,sy);
ans=inf;
ans=min(ans,min(diss[bj[tx][ty]*100+0*3],min(diss[bj[tx][ty]*100+1*3],min(diss[bj[tx][ty]*100+2*3],diss[bj[tx][ty]*100+3*3]))));
if(ans==inf) printf("-1\n");
else printf("%d\n",ans);
}
}