记录编号	584228	评测结果	AAAAAAAAAA
题目名称	[USACO Jan09] 激光电话	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-11-02 22:02:10	内存使用	0.00 MiB

#include <bits/stdc++.h> 
using namespace std;
#define P pair<int,int>
#define mp(x,y) make_pair(x,y)
const int N = 110;
int n,m;
char c[N][N];
int f[N][N][6],fx,fy,ex,ey;//上下左右为1234 
queue<P>q; 
bool check(int x,int y){
    if(x < 1 || x > n || y < 1 || y > m || c[x][y] == '*')return 0;
    return 1;
}
void bfs(){
    q.push(mp(fx,fy));
    while(!q.empty()){
        int x = q.front().first,y = q.front().second;q.pop();bool fl = 0;
        if(check(x-1,y)){
            if(f[x][y][1] < f[x-1][y][1])f[x-1][y][1] = f[x][y][1],fl = 1;
            if(f[x][y][3]+1 < f[x-1][y][1])f[x-1][y][1] = f[x][y][3]+1,fl = 1;
            if(f[x][y][4]+1 < f[x-1][y][1])f[x-1][y][1] = f[x][y][4]+1,fl = 1;
            if(fl)q.push(mp(x-1,y));fl = 0;
        }
        
        if(check(x+1,y)){
            if(f[x][y][2] < f[x+1][y][2])f[x+1][y][2] = f[x][y][2],fl = 1;
            if(f[x][y][3]+1 < f[x+1][y][2])f[x+1][y][2] = f[x][y][3]+1,fl = 1;
            if(f[x][y][4]+1 < f[x+1][y][2])f[x+1][y][2] = f[x][y][4]+1,fl = 1;
            if(fl)q.push(mp(x+1,y));fl = 0;
        }
        
        if(check(x,y-1)){
            if(f[x][y][3] < f[x][y-1][3])f[x][y-1][3] = f[x][y][3],fl = 1;
            if(f[x][y][1]+1 < f[x][y-1][3])f[x][y-1][3] = f[x][y][1]+1,fl = 1;
            if(f[x][y][2]+1 < f[x][y-1][3])f[x][y-1][3] = f[x][y][2]+1,fl = 1;
            if(fl)q.push(mp(x,y-1));fl = 0;
        }
        
        if(check(x,y+1)){
            if(f[x][y][4] < f[x][y+1][4])f[x][y+1][4] = f[x][y][4],fl = 1;
            if(f[x][y][1]+1 < f[x][y+1][4])f[x][y+1][4] = f[x][y][1]+1,fl = 1;
            if(f[x][y][2]+1 < f[x][y+1][4])f[x][y+1][4] = f[x][y][2]+1,fl = 1;
            if(fl)q.push(mp(x,y+1));fl = 0;
        }
    }
}
int main(){
    freopen("lphone.in","r",stdin);
    freopen("lphone.out","w",stdout);
    scanf("%d%d",&m,&n);
    for(int i = 1;i <= n;i++){
        scanf("%s",c[i]+1);
        int l = strlen(c[i]+1);
        for(int j = 1;j <= l;j++){
            if(c[i][j] == 'C'){
                if(!fx)fx = i,fy = j;
                else ex = i,ey = j;
            }
        }
    } 
    memset(f,0x3f,sizeof(f));
    for(int i = 1;i <= 4;i++)f[fx][fy][i] = 0;
    bfs();
    printf("%d\n",min(f[ex][ey][1],min(f[ex][ey][2],min(f[ex][ey][3],f[ex][ey][4]))));
    
    return 0;
    
}