专栏文章

题解：CF2041D Drunken Maze

cccjjxx
CF2041D题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqzjkm1
此快照首次捕获于
2025/12/04 13:18
3 个月前
此快照最后确认于
2025/12/04 13:18
3 个月前
查看原文
图论题，考完发现都写的是 dijkstra，但是我写的是 BFS。
首先先正常写，然后对于每个状态记录现在的方向和朝这个方向连续走了多少次，显然，当次数等于 44 时，你需要换方向，如果要沿同一防线继续走，就需要后退一步再前进两步。
这时就有 hack 来卡我了，如果按照这种方式连续朝同一方向前进，那么这样后退再前进的花费会是 22，也就是消耗了一次向前走的机会。但是，如果现在的左右（或上下）有空格子，你可以向别的方向换一下，再朝原方向前进，这样花费是 11。举个例子：
CPP
S.........T
...........
这样的路，你可以直接直线行走，也可以向前走两格再向下移动，再回来，是更优的。
有个细节，就是优先队列中有位置相同，答案相同，但是方向来源不同的点，为了保证正确性，你需要把符合这些条件的所有点全部跑出来，而不是只取第一个，有这样一个 hack 数据，找到了我在赛时的错误（来自 Baiyj）。
CPP
5 18
S................T
.################.
.################.
..##....##....##..
..................
附上有很多 hack 数据的代码：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
int stx,sty,edx,edy;
struct node{
	int x,y;
	int val,f;
	int pre,prepos;
	inline bool operator<(const node &ll) const
	{
		if(x==ll.x&&pre==ll.pre&&val==ll.val) return y>ll.y;
		if(pre==ll.pre&&val==ll.val) return x>ll.x;
		if(val==ll.val) return pre>ll.pre;
		return val>ll.val;
	}
};
priority_queue<node>q;
int dx[5]={0,0,1,-1,0};
int dy[5]={0,1,0,0,-1};
inline int man(int a,int b,int x,int y)
{
	return abs(a-b)+abs(x-y);
}
signed main()
{
	cin>>n>>m;
	vector<vector<bool>> vis(n+5,vector<bool>(m+5,0)),mp(n+5,vector<bool>(m+5,0));
	for(int i=1;i<=n;i++)
	{
		string c;cin>>c;
		for(int j=0;j<m;j++) 
		{
			mp[i][j+1]=0,vis[i][j+1]=0;
			if(c[j]=='#') mp[i][j+1]=1;
			if(c[j]=='S') stx=i,sty=j+1;
			if(c[j]=='T') edx=i,edy=j+1;
		}
	}
	q.push({stx,sty,0,man(stx,sty,edx,edy),0,0});
	int ans=1e9;
	while(!q.empty())
	{
		node now=q.top();q.pop();
		
		if(now.x==edx&&now.y==edy)
		{
			ans=min(ans,now.val);
			break;
		}
		if(vis[now.x][now.y]) continue;
		vis[now.x][now.y]=1;
		bool tt=0;
		do
		{
			if(tt) now=q.top(),q.pop();
			tt=1;
			for(int i=1;i<=4;i++)
			{
				node nxt=now;
				nxt.x+=dx[i],nxt.y+=dy[i];
				if(nxt.x<1||nxt.y<1||nxt.x>n||nxt.y>m||mp[nxt.x][nxt.y]) continue;
				if(i==nxt.prepos) nxt.pre++;
				else nxt.pre=0;
				nxt.val++;
				if(nxt.pre==3) 
				{
					if(i==2||i==3)
					{
						node nxx=now;
						nxx.x+=dx[1],nxx.y+=dy[1];
						if(!(nxx.x<1||nxx.y<1||nxx.x>n||nxx.y>m||mp[nxx.x][nxx.y]))
						{
							nxt.pre=0,nxt.val+=2;
						}
						else
						{
							nxx=now;
							nxx.x+=dx[4],nxx.y+=dy[4];
							if(!(nxx.x<1||nxx.y<1||nxx.x>n||nxx.y>m||mp[nxx.x][nxx.y]))
								nxt.pre=0,nxt.val+=2;
							else nxt.val+=2,nxt.pre=1;
						}
					}
					else
					{
						node nxx=now;
						nxx.x+=dx[2],nxx.y+=dy[2];
						if(!(nxx.x<1||nxx.y<1||nxx.x>n||nxx.y>m||mp[nxx.x][nxx.y]))
						{
							nxt.pre=0,nxt.val+=2;
						}
						else
						{
							nxx=now;
							nxx.x+=dx[3],nxx.y+=dy[3];
							if(!(nxx.x<1||nxx.y<1||nxx.x>n||nxx.y>m||mp[nxx.x][nxx.y]))
								nxt.pre=0,nxt.val+=2;
							else nxt.val+=2,nxt.pre=1;
						}
					}
				}
				else nxt.prepos=i;
				nxt.f=nxt.val+man(nxt.x,nxt.y,edx,edy);
				q.push(nxt);
			}
		}while(q.top().x==now.x&&q.top().y==now.y&&q.top().val==now.val&&q.top().prepos!=now.prepos);
	}
	if(ans==1e9)
	cout<<"-1";
	else cout<<ans;
}
/*
6 5
.S#..
#.#..
.....
#.#..
.....
.#..T
 
2 12
S..........T
.##..#..##..
 
2 7
S.....T
....##.
 
#..#..
S.....
##..#
 
5 8
S....#T.
#...#.#.
#.#.....
#...##..
##......
 
7 12
############
#S.........#
#####.######
#T..#.######
#...#.######
#.....######
############
 
5 7
S....#T
.#.#.#.
.#.#.#.
.#.#.#.
.......
 
2 10
S........T
##.####..#
 
5 18
S................T
.################.
.################.
..##....##....##..
..................
 
*/

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...