比赛 |
动态规划练习赛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;
}