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

/* 
8 8
C**...**
....*...
.******.
*.......
*.******
*......*
.*****.*
*C.....*
*/
    #include<bits/stdc++.h>
    using namespace std;
    int n,m,s=0x3f3f3f3f;
    int a[110][110];
    int f[110][110][5];//上下左右 
    int ix,iy,sx,sy;
    queue<pair<int,int> >q;
    void bfs(){
        memset(f,0x3f,sizeof(f));
        f[ix][iy][1]=0,f[ix][iy][2]=0,f[ix][iy][3]=0,f[ix][iy][4]=0;
        q.push(make_pair(ix,iy));
        while(!q.empty()){
             int x=q.front().first;
             int y=q.front().second;    
             q.pop();   
             if(x+1<=n&&a[x+1][y]==0){ 
             int o=0; 
                if(f[x][y][2]<f[x+1][y][2]){
                     f[x+1][y][2]=f[x][y][2];
                     o=1;
              } 
              if(f[x][y][3]+1<f[x+1][y][2]){
                     f[x+1][y][2]=f[x][y][3]+1;
              o=1;
              }
              if(f[x][y][4]+1<f[x+1][y][2]){
              f[x+1][y][2]=f[x][y][4]+1;
              o=1;}
              if(o)q.push(make_pair(x+1,y));
             }
             if(x-1>=1&&a[x-1][y]==0){int o=0;
             if(f[x][y][1]<f[x-1][y][1]){
                     f[x-1][y][1]=f[x][y][1];o=1;
              } 
              if(f[x][y][3]+1<f[x-1][y][1]){
                     f[x-1][y][1]=f[x][y][3]+1;o=1;
              }
              if(f[x][y][4]+1<f[x-1][y][1]){
              f[x-1][y][1]=f[x][y][4]+1;o=1;
               
              }
              if(o)q.push(make_pair(x-1,y));
             }
             if(y+1<=m&&a[x][y+1]==0){int o=0;
                if(f[x][y][4]<f[x][y+1][4]){
                     f[x][y+1][4]=f[x][y][4];o=1;
              } 
              if(f[x][y][2]+1<f[x][y+1][4]){
                     f[x][y+1][4]=f[x][y][2]+1;o=1;
              }
              if(f[x][y][1]+1<f[x][y+1][4]){
              f[x][y+1][4]=f[x][y][1]+1;o=1;
               
              }
              if(o)q.push(make_pair(x,y+1));
             }
             if(y-1>=1&&a[x][y-1]==0){int o=0;
                if(f[x][y][3]<f[x][y-1][3]){
                     f[x][y-1][3]=f[x][y][3];o=1;
                     
              } 
              if(f[x][y][1]+1<f[x][y-1][3]){
                     f[x][y-1][3]=f[x][y][1]+1;o=1;
              }
              if(f[x][y][2]+1<f[x][y-1][3]){
              f[x][y-1][3]=f[x][y][2]+1;o=1;
              }
              if(o)q.push(make_pair(x,y-1));
             }
        }
        cout<<min(f[sx][sy][1],min(f[sx][sy][2],min(f[sx][sy][3],f[sx][sy][4])));
    } 
    int main(){
        freopen("lphone.in","r",stdin);
        freopen("lphone.out","w",stdout);
          cin>>m>>n;
          for(int i=1;i<=n;i++){
              for(int j=1;j<=m;j++){
                  char o;
                  cin>>o;
                  if(o=='*'){
                      a[i][j]=1;
                  }
                  if(o=='C'){
                      if(!ix){
                          ix=i;
                          iy=j;
                      }else{
                          sx=i;
                          sy=j;
                      }
                  }
              }
          }
          bfs();
    }