luoguP1300 城市街道交通费系统

爆搜+优化

注意:同一个地方只能转一次弯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <unordered_map>//C++11哈希表实现的map
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1},inf=0x3f3f3f3f;
unordered_map<char,int> char2digit = {{'N',0},{'S',2},{'E',1},{'W',3}};//字母方向转换成数字
unordered_map<int,char> digit2char = {{0,'N'},{2,'S'},{1,'E'},{3,'W'}};//数字方向转换成字母(调试用)
int h,w,mem[40][40][4];//mem[i][j][k]:(i,j)处方向为k时的花费最小值
pair<int,int> from,to;
char mp[40][40];
inline int lturn(int x){//当前方向x左转90°后的方向
int y = x - 1;
return y==-1?3:y;
}
inline int rturn(int x){//当前方向x右转90°后的方向
int y = x + 1;
return y==4?0:y;
}
inline int turnAround(int x){//当前方向x掉头后的方向
int y = x + 2;
return y % 4;
}
inline bool canWalkThrough(int x,int y,int dir){//当前位置(x,y)能否向dir方向移动一格
return mp[x+dx[dir]][y+dy[dir]]!='.';
}
void dfs(int x,int y,int cost,int dir){//大法师(误)x,y为当前坐标,cost为当前花费,dir为当前方向
if(cost>=mem[x][y][dir]) return;//剪枝
mem[x][y][dir] = cost;//更新标记数组
if(x==to.first&&y==to.second) return;//如果到达终点直接返回(上一行已经保存最小花费)
bool flag=false;
if(canWalkThrough(x,y,dir))//如果能直走
dfs(x+dx[dir],y+dy[dir],cost,dir),flag=true;//直走
int l=lturn(dir),r=rturn(dir);
if(canWalkThrough(x,y,l))//如果能左转
dfs(x+dx[l],y+dy[l],cost+1,l),flag=true;//左转
if(canWalkThrough(x,y,r))//如果能右转
dfs(x+dx[r],y+dy[r],cost+5,r),flag=true;//右转
if(!flag){//如果都不行
int back = turnAround(dir);
dfs(x,y,cost+10,back);//掉头
}
}
int main(){
memset(mem,inf,sizeof(mem));//初始化
cin >> h >> w;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
cin >> mp[i][j];
if(isalpha(mp[i][j])){
if(mp[i][j]=='F') to = {i,j};
else from = {i,j};
}
}
}
dfs(from.first,from.second,0,char2digit[mp[from.first][from.second]]);
cout << min(mem[to.first][to.second][0],min(mem[to.first][to.second][1],min(mem[to.first][to.second][2],mem[to.first][to.second][3]))) << endl;//输出终点四个方向中的最小值
return 0;
}

luoguP1300 城市街道交通费系统
https://www.d0j1a1701.cc/p/dfdbd233/
作者
d0j1a_1701
发布于
2021年1月28日
许可协议
CC-BY-SA