比赛 动态规划练习赛1102 评测结果 RRRRRRRRRR
题目名称 地图着色 最终得分 0
用户昵称 宇战 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2023-11-02 20:23:51
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int n,m,s=0x3f3f3f3f;
int a[110][110];
int f[110][110];
int ix,iy,sx,sy;
void dfs(int x,int y,int z,int step){//最后一个镜子的坐标和反光的方向(1,2,3,4上下左右)以及镜子的个数 
    if(x==sx&&y==sy){
        s=min(s,step);
        return;
    }
    if(z==0){
        if(a[x+1][y]==0&&x+1<=n&&f[x+1][y]==0){
           f[x+1][y]=1;
           dfs(x+1,y,3,step+1);
           dfs(x+1,y,2,step);
           dfs(x+1,y,4,step+1);
           f[x+1][y]=0;
        }
        if(a[x-1][y]==0&&x-1>0&&f[x-1][y]==0){
           f[x-1][y]=1;
           dfs(x-1,y,3,step+1);
           dfs(x-1,y,1,step);
           dfs(x-1,y,4,step+1);
           f[x-1][y]=0;
       }
       if(a[x][y+1]==0&&y+1<=m&&f[x][y+1]==0){
           f[x][y+1]=1;
           dfs(x,y+1,1,step+1);
           dfs(x,y+1,4,step);
           dfs(x,y+1,2,step+1);
           f[x][y+1]=0;
       }
       if(a[x][y-1]==0&&y-1>0&&f[x][y-1]==0){
           f[x][y-1]=1;
           dfs(x,y-1,1,step+1);
           dfs(x,y-1,3,step);
           dfs(x,y-1,2,step+1);
           f[x][y-1]=0;
       }
    }
    if(z==1){
       if(a[x-1][y]==0&&x-1>0&&f[x-1][y]==0){
           f[x-1][y]=1;
           dfs(x-1,y,3,step+1);
           dfs(x-1,y,1,step);
           dfs(x-1,y,4,step+1);
           f[x-1][y]=0;
       }
    }
    if(z==2){
       if(a[x+1][y]==0&&x+1<=n&&f[x+1][y]==0){
           f[x+1][y]=1;
           dfs(x+1,y,3,step+1);
           dfs(x+1,y,2,step);
           dfs(x+1,y,4,step+1);
           f[x+1][y]=0;
        }
    }
    if(z==3){if(a[x][y-1]==0&&y-1>0&&f[x][y-1]==0){
           f[x][y-1]=1;
           dfs(x,y-1,1,step+1);
           dfs(x,y-1,3,step);
           dfs(x,y-1,2,step+1);
           f[x][y-1]=0;
       }
        
    }
    if(z==4){
       if(a[x][y+1]==0&&y+1<=m&&f[x][y+1]==0){
           f[x][y+1]=1;
           dfs(x,y+1,1,step+1);
           dfs(x,y+1,4,step);
           dfs(x,y+1,2,step+1);
           f[x][y+1]=0;
       }
       
    }
    
}
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;
                  }
              }
          }
      }
      dfs(ix,iy,0,0);
      cout<<s;
}