2021.08.16 P1300 城市街道交通费系统（dfs）

2021.08.16 P1300 城市街道交通费系统（dfs）

P1300 城市街道交通费系统 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：

城市街道交费系统最近创立了。一辆汽车左转一次需付费 11 ，右转一次需付费 55 。只有当前进、左转、右转都无路可走的时候，调头才是允许的，调头每次付费 1010 。

给出一张城市地图，要求你求出从起始点到达终止点的花费最少的路径。幸运的是，所有的道路都是正北、正南、正西或正东方向的。

. 表示障碍区。
# 表示道路。
E 表示起始点且汽车面朝东。
W 表示起始点且汽车面朝西。
N 表示起始点且汽车面朝北。
S 表示起始点且汽车面朝南。
F 表示终点。

代码如下：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=55;

const int inf=0x3f3f3f;

int n,m,startx,starty,startflag,minn[N][N][4],ans=inf;

char map[N][N];

int disx[5]={-1,0,1,0},disy[5]={0,1,0,-1};

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

void dfs(int x,int y,int flag,int v){

	if(map[x][y]=='F'){

		ans=min(ans,v);

		return ;

	}

	if(minn[x][y][flag]<=v||ans<=v)return ;

	minn[x][y][flag]=v;

	bool fin=1;

	/*for(int i=0;i<4;i++){

		int xi=disx[i]+x,yi=disy[i]+y;

		if(xi<1||xi>n||yi<1||yi>m||map[xi][yi]=='.')continue;

		if(flag==i)dfs(xi,yi,flag,v),fin=0;

		else if((flag+1)%4==i)dfs(xi,yi,(flag+1)%4,v+5),fin=0;

		else if((flag-1+4)%4==i)dfs(xi,yi,(flag+3)%4,v+1),fin=0;

		else if(fin)dfs(xi,yi,(flag+2)%4,v+10),fin=0;

	}*/

	//啊，对了，万一掉头的方位是0，而其他的方位是1、2、3呢？

	for(int i=0;i<4;i++){

		int xi=x+disx[i],yi=y+disy[i];

		if(xi<1||xi>n||yi<1||yi>m||map[xi][yi]=='.')continue;

		if(flag==i)dfs(xi,yi,i,v),fin=0;

	}

	for(int i=0;i<4;i++){

		int xi=x+disx[i],yi=y+disy[i];

		if(xi<1||xi>n||yi<1||yi>m||map[xi][yi]=='.')continue;

		if((flag+1)%4==i)dfs(xi,yi,i,v+5),fin=0;

	}

	for(int i=0;i<4;i++){

		int xi=x+disx[i],yi=y+disy[i];

		if(xi<1||xi>n||yi<1||yi>m||map[xi][yi]=='.')continue;

		if((flag+3)%4==i)dfs(xi,yi,i,v+1),fin=0;

	}

	if(fin){

		for(int i=0;i<4;i++){

			int xi=x+disx[i],yi=y+disy[i];

			if(xi<1||xi>n||yi<1||yi>m||map[xi][yi]=='.')continue;

			if((flag+2)%4==i)dfs(xi,yi,i,v+10),fin=0;

		}

	}

}

int main(){

	memset(minn,inf,sizeof(minn));

	n=read();m=read();

	for(int i=1;i<=n;i++){

		scanf("%s",map[i]+1);

		for(int j=1;j<=m;j++){

			if(map[i][j]=='E')startx=i,starty=j,startflag=1;

			else if(map[i][j]=='W')startx=i,starty=j,startflag=3;

			else if(map[i][j]=='N')startx=i,starty=j,startflag=0;

			else if(map[i][j]=='S')startx=i,starty=j,startflag=2;

		}

	}

	/*for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++)cout<<map[i][j]<<" ";

		cout<<endl;

	}

	cout<<endl;*/

	dfs(startx,starty,startflag,0);

	cout<<ans;

	return 0;

}

2021.08.16 P1300 城市街道交通费系统（dfs）的相关教程结束。