58分,TLE+WA#10,自己举不出反例
查看原帖
58分,TLE+WA#10,自己举不出反例
1186230
liwenliwenllll楼主2024/4/23 23:59

评论区翻了很久,说不需要对传送门标记。但是我标记传送起点的话(传送终点没有被标记),依然可以从传送终点回到传送起点。真的想不到反例了,求助大佬58分

#include <bits/stdc++.h>
using namespace std;
int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};
char mp[105][105];
int cnt[305][305];
int ans,n,m,nx,ny;
bool vis[305][305];
pair<int,int>node;
deque<pair<int,int> >dq;
void getAnother(char ch)
{
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
			if(mp[i][j] == ch && !(i == nx && j == ny))
			{
				nx = i;
				ny = j;
				return;
			}
		}
}
void bfs(int sx,int sy)
{
	vis[sx][sy] = true;
	pair<int,int> start; start.first = sx,start.second = sy;
	dq.push_back(start);
	while(!dq.empty())
	{
		int x = dq.front().first,y = dq.front().second;
		if(mp[x][y] == '@')
		{
			ans = cnt[x][y];
			return;
		}
		for(int i = 0 ; i < 4; i++)
		{
			nx = x + dx[i],ny = y + dy[i];
			if(nx >= 1 && nx <= 300 && ny >= 1 && ny <= 300 && !vis[nx][ny] && mp[nx][ny] != '#')
			{
				vis[nx][ny] = true;	//如果是传送门,则标记的是传送起点的点,不影响传送后从当前的传送终点再回到传送起点,因为传送终点仍然是false 
				if(mp[nx][ny] >= 'A' && mp[nx][ny] <= 'Z') getAnother(mp[nx][ny]);//强行传送至下一传送门
				cnt[nx][ny] = cnt[x][y] + 1;	//如果是传送后,则传送后的门cnt为传送前的位置+1 
				dq.push_back({nx,ny});	//果是传送后,则加入队列的点是传送后的点 
			}
		}
		dq.pop_front();
	}
}
int main()
{
	cin>>n>>m;
	int x,y;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
			cin>>mp[i][j];
			if(mp[i][j] == '=')
			{
				x = i;
				y = j;
			}
		}
	bfs(x,y);	
	cout<<ans;
//	打印cnt数组 
//	cout<<endl;
//	for(int i = 1; i <= n; i++)
//	{
//		for(int j = 1; j <= m; j++) cout<<cnt[i][j];
//		cout<<endl;
//	}	
	return 0;
} 
2024/4/23 23:59
加载中...