自动搬运

查看原文

来自洛谷，原作者为

	RedreamMer 一拍桌子，两眼放光，三十分钟，四百分贝，五指指天，六重积分，七次反演，八维凸包，九只 log，十种做法，全部假啦！！！

搬运于2025-08-24 21:23:30，当前版本为作者最后更新于2019-11-15 10:09:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P1300题解

算法： $BFS$

为什么题解里的人们都是用DFS写的QAQ，一定是我太菜了

这类题目很明显要用搜索做，好像这道题并不会卡 $DFS$ ，但我还是用 $BFS$ 顽强地做了下去

第一步，把数据读入并存储在一张图里，能走标记为 $1$ ，不能走标记为 $0$ ，再记录一下起点和终点，注意要标记起点的方向，用优先队列维护，以花费为关键字把最小的放在队首，这部分就做完了

第二步，开始 $BFS$ ，把当前所有能做的步骤都做一遍，即前进、左转、右转、掉头（当前面都不能做时才能做，不然会 $WA$ 一个点），还有，如果当前能做某个步骤，但做了之后不是最优的，那就不要做了，但不做不代表不能做，所以我们要造一个数组来维护当前的最优花费： $m[i][j][k]$ （ $i$ ， $j$ 代表坐标 $x$ ， $y$ ， $k$ 代表方向（$k\in[0,3]$）），由于有优先队列维护作用，所以先访问到终点就是最快的，直接跳出

第三步，输出 $Answer$

code：

#include<bits/stdc++.h>
using namespace std;
int a,b,xx,yy,x,y;
int dx[4]= {-1,0,1,0},dy[4]= {0,1,0,-1};//方向数组，很方便 
int m[1001][1001][4];//数组维护花费 
bool s[1001][1001];
char ch;
struct P {//协助优先队列 
	int x,y,to;
	bool operator<(const P& t)const {//优先规则 
		return m[t.x][t.y][t.to]<m[x][y][to];
	}
} k,l;
priority_queue<P> st;
int main() {
	memset(m,0x7f,sizeof m);//初始化 
	cin>>a>>b;
	for(int i=1; i<=a; i++)//读入 
		for(int j=1; j<=b; j++) {
			cin>>ch;
			if(ch!='.') {
				s[i][j]=1;
				if(ch!='#') {
					if(ch!='F') {
						if(ch=='N')
							k.to=0;
						if(ch=='S')
							k.to=2;
						if(ch=='W')
							k.to=3;
						if(ch=='E')
							k.to=1;
						k.x=i;
						k.y=j;
					} else {
						xx=i;
						yy=j;
					}
				}
			}
		}
	m[k.x][k.y][k.to]=0;
	st.push(k);
	while(!st.empty()) {//BFS开始 
		bool q=0;
		k=st.top();
		if(k.x==xx&&k.y==yy)//访问到终点 
		break;
		st.pop();
		x=k.x+dx[k.to];
		y=k.y+dy[k.to];
		if(s[x][y])
			q=1;
		if(s[x][y]&&m[x][y][k.to]>m[k.x][k.y][k.to]) {//前进判断 
			m[x][y][k.to]=m[k.x][k.y][k.to];
			l.x=x;
			l.y=y;
			l.to=k.to;
			st.push(l);
		}
		x=k.x+dx[(k.to+3)%4];
		y=k.y+dy[(k.to+3)%4];
		if(s[x][y])
			q=1;
		if(s[x][y]&&m[x][y][(k.to+3)%4]>m[k.x][k.y][k.to]+1) {//左转判断 
			m[x][y][(k.to+3)%4]=m[k.x][k.y][k.to]+1;
			l.x=x;
			l.y=y;
			l.to=(k.to+3)%4;
			st.push(l);
		}
		x=k.x+dx[(k.to+1)%4];
		y=k.y+dy[(k.to+1)%4];
		if(s[x][y])
			q=1;
		if(s[x][y]&&m[x][y][(k.to+1)%4]>m[k.x][k.y][k.to]+5) {//右转判断 
			m[x][y][(k.to+1)%4]=m[k.x][k.y][k.to]+5;
			l.x=x;
			l.y=y;
			l.to=(k.to+1)%4;
			st.push(l);
		}
		if(!q) {//判断其他操作能不能做 
			x=k.x+dx[(k.to+2)%4];
			y=k.y+dy[(k.to+2)%4];
			if(s[x][y]&&m[x][y][(k.to+2)%4]>m[k.x][k.y][k.to]+10) {//后退判断 
				m[x][y][(k.to+2)%4]=m[k.x][k.y][k.to]+10;
				l.x=x;
				l.y=y;
				l.to=(k.to+2)%4;
				st.push(l);
			}
		}
	}
	cout<<m[k.x][k.y][k.to];
	return 0;
}//97行代码QAQ 

$46ms$ 快得起飞

$\color{blue}\text{My Blog}$