【题解】洛谷P1300 城市街道交通费系统

爆搜+优化

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

#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;
}