为什么传送站不需要打标机
查看原帖
为什么传送站不需要打标机
1053122
liruizhou_lihui楼主2025/2/5 12:24

打了标记:https://www.luogu.com.cn/record/201376314

没打标记:https://www.luogu.com.cn/record/201376415

这是我没打标记的

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=1e8;
bool vis[305][305];
int ax,ay,bx,by;
char a[305][305];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
vector<int> v[150];
struct qaq
{
	int x,y,t;
};
queue<qaq> q;
map<pair<int,int>,pair<int,int>> mp;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='@')
			{
				ax=i;
				ay=j;
			}
			if(a[i][j]=='=')
			{
				bx=i;
				by=j;
			}
			if(a[i][j]>='A'&&a[i][j]<='Z')
			{
				//cout<<"qwq";
				v[(int)a[i][j]].push_back(i);
				v[(int)a[i][j]].push_back(j);
			}
		}
	}
//	for(int i:v['W'])
//	{
//		cout<<i<<' ';
//	}
//	cout<<'\n';
	for(int qwq='A';qwq<='Z';qwq++)
	{
		if(v[qwq].size()!=0)
		{
			int i=v[qwq][0];
			int j=v[qwq][1];
			int ii=v[qwq][2];
			int jj=v[qwq][3];
			mp[make_pair(i,j)]=make_pair(ii,jj);
			mp[make_pair(ii,jj)]=make_pair(i,j);
		}
	}
	vis[ax][ay]=1;
	q.push({ax,ay,0});
	while(!q.empty())
	{
		qaq now=q.front();
		q.pop();
		if(now.x==bx && now.y==by)
		{
			ans=min(ans,now.t);
			continue;
		}
		if(a[now.x][now.y]>='A'&&a[now.x][now.y]<='Z')
		{
			int x=mp[make_pair(now.x,now.y)].first;
			int y=mp[make_pair(now.x,now.y)].second;
			//cout<<"awa"<<' '<<x<<' '<<y<<'\n';
			//vis[x][y]=1;
			for(int i=0;i<4;i++)
			{
				int ii=x+dx[i];
				int jj=y+dy[i];
				if(ii>=1&&ii<=n&&jj>=1&&jj<=m&&(!vis[ii][jj]||(ii==bx&&jj==by))&&a[ii][jj]!='#')
				{
					q.push({ii,jj,now.t+1});
					vis[ii][jj]=1;
					//cout<<ii<<' '<<jj<<"qaq\n";
				}
			}
		}
		else
		{
			for(int i=0;i<4;i++)
			{
				int ii=now.x+dx[i];
				int jj=now.y+dy[i];
				if(ii>=1&&ii<=n&&jj>=1&&jj<=m&&!vis[ii][jj]&&a[ii][jj]!='#')
				{
					q.push({ii,jj,now.t+1});
					vis[ii][jj]=1;
					//cout<<ii<<' '<<jj<<"awa\n";
				}
			}
		}
	}
	cout<<ans;
	return 0;
}

vis[x][y]=1的注释取消就变成没打标记的了

2025/2/5 12:24
加载中...