分层图+堆优化的dijkstra
将原图分为4层,分别是只向上,向下,向左,向右建立边,然后层与层之间的转移很好处理。稠密图,应该用堆优化的dijkstra。
//OJ 1845 //by Cydiater //2016.10.8 #include <iostream> #include <cstring> #include <string> #include <algorithm> #include <queue> #include <map> #include <ctime> #include <cmath> #include <cstdlib> #include <cstdio> #include <iomanip> using namespace std; #define ll long long #define up(i,j,n) for(int i=j;i<=n;i++) #define down(i,j,n) for(int i=j;i>=n;i--) #define pii pair<int,int> #define mp make_pair const int MAXN=1e6+5; const int oo=0x3f3f3f3f; const int dx[4]={-1,0,1,0}; const int dy[4]={0,1,0,-1}; inline int read(){ char ch=getchar();int x=0,f=1; while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int N,M,node[105][105][4],cnt=0,LINK[MAXN],len=0,dis[MAXN],ans=oo; /* 0 3 1 2 */ pii S,T; bool a[1005][1005],vis[MAXN]; struct edge{ int y,next,v; }e[MAXN<<1]; priority_queue<pii,vector<pii>,greater<pii> >q; namespace solution{ inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;} void init(){ M=read();N=read(); up(i,1,N){ scanf("\n"); up(j,1,M){ char ch;scanf("%c",&ch); a[i][j]=ch=='*'?0:1; if(ch=='C'){ if(S.first==0)S=mp(i,j); else T=mp(i,j); } } } up(i,1,N)up(j,1,M)up(k,0,3)node[i][j][k]=++cnt; up(i,1,N)up(j,1,M)if(a[i][j])up(k,0,3){ int aim=(k+1)%4,tx=i+dx[k],ty=j+dy[k]; if(a[tx][ty]){ insert(node[i][j][k],node[tx][ty][k],0); //cout<<i<<' '<<j<<' '<<k<<endl; } if(mp(i,j)!=S&&mp(i,j)!=T){ insert(node[i][j][k],node[i][j][aim],1);aim=(k+3)%4; insert(node[i][j][k],node[i][j][aim],1); } } } void Dijkstra(int st){ memset(vis,0,sizeof(vis)); memset(dis,10,sizeof(dis)); dis[st]=0;q.push(mp(dis[st],st)); while(!q.empty()){ pii tmp=q.top();q.pop(); int node=tmp.second; if(vis[node])continue; vis[node]=1; for(int i=LINK[node];i;i=e[i].next) if(dis[e[i].y]>dis[node]+e[i].v){ dis[e[i].y]=dis[node]+e[i].v; q.push(mp(dis[e[i].y],e[i].y)); } } } void slove(){ up(i,0,3){ Dijkstra(node[S.first][S.second][i]); up(j,0,3)ans=min(ans,dis[node[T.first][T.second][j]]); } cout<<ans<<endl; } } int main(){ //freopen("input.in","r",stdin); //freopen("out.out","w",stdout); using namespace solution; init(); slove(); return 0; }