自动搬运

查看原文

来自洛谷，原作者为

	Liyx NO GAME NO LIFE

搬运于2025-08-24 21:28:28，当前版本为作者最后更新于2024-07-09 17:09:58，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

第一眼是一道 BFS，直到看到了天堂之门。所以用 DFS 写了一下，直接 TLE40。记录

相信各位停留在 A 处和 B 处的代码都会写，所以来讲一下停留在 C 处的代码。

在 C 处要停一步再走，所以可以定义一个 $flag$，当到了 C 处时，判断 $flag$ 是否为 $1$，如果为 $0$，将 $flag$ 修改为 $1$，并将步数也加 $1$，然后重新加入到队列里，这样可以做到停一步的效果；如果为 $1$，说明已经停留过了，所以正常的进行 BFS 就好了。

最后放上 AC 代码。

代码

#include <bits/stdc++.h>
using namespace std;
int n;
char a[1205][1205];
bool vis[1205][1205];
int d1[2][5]={{1,0,-1,0},{0,1,0,-1}};
int d3[2][5]={{1,1,-1,-1},{-1,1,1,-1}};
struct node{
	int x,y,step;
	bool flag;
};
bool flag;
void bfs(){
	queue<node> q;
	if(a[1][1]!='*') q.push(node{1,1,1,0});
	if(a[1][n]!='*') q.push(node{1,n,1,0});
	if(a[n][1]!='*') q.push(node{n,1,1,0});
	while(!q.empty()){
		node now=q.front();
		q.pop();
		if(now.x==n&&now.y==n){
			//标记 
			flag=1;
			cout<<now.step;
			return;
		}
		if(a[now.x][now.y]=='A'){
			for(int i=0;i<4;i++){
				int xx=now.x+d1[0][i],yy=now.y+d1[1][i];
				if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&!vis[xx][yy]&&a[xx][yy]!='*'){
					vis[xx][yy]=1;
					q.push(node{xx,yy,now.step+1,0});
				}
			}
		}
		else if(a[now.x][now.y]=='B'){
			for(int i=0;i<4;i++){
				//在B处会传送2格，乘以2 
				int xx=now.x+2*d1[0][i],yy=now.y+2*d1[1][i];
				if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&!vis[xx][yy]&&a[xx][yy]!='*'){
					vis[xx][yy]=1;
					q.push(node{xx,yy,now.step+1,0});
				}
			}
		}
		else if(a[now.x][now.y]=='C'){
			//对于聚气的处理 
			if(now.flag==0){
				q.push(node{now.x,now.y,now.step+1,1});
				continue;
			}
			
			//flag不为0则正常进行BFS 
			for(int i=0;i<4;i++){
				int xx=now.x+d3[0][i],yy=now.y+d3[1][i];
				if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&!vis[xx][yy]&&a[xx][yy]!='*'){
					vis[xx][yy]=1;
					q.push(node{xx,yy,now.step+1,0});
				}
			}
		}
	}
	
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) cin>>a[i][j];
	//如果a[n][n]本身为障碍则无解 
	if(a[n][n]=='*'){
		cout<<"No answer";
		return 0;
	}
	bfs();
	//如果没有输出则无解 
	if(flag==0){
		cout<<"No answer";
		return 0;
	}
	return 0;
}