分层图+堆优化的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;
}