比赛 |
动态规划练习赛1102 |
评测结果 |
AAAAAAAAAA |
题目名称 |
激光电话 |
最终得分 |
100 |
用户昵称 |
┭┮﹏┭┮ |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2023-11-02 19:30:42 |
显示代码纯文本
#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;
// cout<<fx<<' '<<fy<<endl;
// cout<<ex<<' '<<ey<<endl;
bfs();
// cout<<1<<endl;
printf("%d\n",min(f[ex][ey][1],min(f[ex][ey][2],min(f[ex][ey][3],f[ex][ey][4]))));
return 0;
}