【题解】洛谷P7775

感谢@xiejinghan在赛时给我分享思路。

题目传送门

题意简述

在一个二维矩阵上面，从V到J的路径中，求离+的最短距离。

解题步骤

题目中写离它最近的树的距离的最小值，很明显就能想到二分。

在读入数据时，用startx和starty标记起点的坐标。

同时，用endx和endy标记窝的坐标。

这里$dtt_{i,j}$表示$i,j$到树的最短距离

接着，使用bfs的方式，对$dtt$进行处理。

（顾名思义，$dtt_{i,j}$就是坐标$i,j$的点到最近的一棵树的最短距离）

然后特判，如果起点和窝的位置重合，就直接输出$dtt_{startx,starty}$。

接下来使用二分的技巧，$l=0,r=1000$，然后while循环二分查找直到$l \geq r$。

如何查找？

就是用双向广搜，也就是从起点和窝同时进行广搜。

在进行双向bfs的过程中，vis的状态变成了$0,1,2$。

其中的$0$表示没有访问到，$1$表示这是起点过来访问到的，$2$表示窝过来访问到的。

bfs直到下一个点的状态（$vis_{nx,ny}$）与当前点的状态（$vis_{x,y}$）不相同，返回$1$。

（在这之前一定要判断$vis_{nx,ny} \neq 0$）

否则返回$0$。

代码部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
using namespace std;
const int MAXN=510;
int n,m,dis_to_tree[MAXN][MAXN],startx,starty,endx,endy;
int vis[MAXN][MAXN];
char mp[MAXN][MAXN];
struct node
{
	int x,y,to_tree_dis,type;
};
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
void search1()
{
	memset(dis_to_tree,-1,sizeof(dis_to_tree));
	memset(vis,0,sizeof(vis));
	queue<node> q;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(mp[i][j]=='+')
			{
				dis_to_tree[i][j]=0;
				vis[i][j]=1;
				q.push({i,j,0,0});
			}
		}
	}
	while(!q.empty())
	{
		node top=q.front();
		q.pop();
		int x=top.x,y=top.y;
		for(int i=0;i<4;i++)
		{
			int nx=x+dx[i],ny=y+dy[i];
			if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&!vis[nx][ny])
			{
				dis_to_tree[nx][ny]=top.to_tree_dis+1;
				vis[nx][ny]=1;
				q.push({nx,ny,dis_to_tree[nx][ny],0});
			}
		}
	}
}
bool solve(int dis)
{
	if(dis==0) return 1;
	memset(vis,0,sizeof(vis));
	queue<node> q;
	if(dis_to_tree[startx][starty]<dis||dis_to_tree[endx][endy]<dis) return 0;
	q.push({startx,starty,0,1});
	q.push({endx,endy,0,2});
	vis[startx][starty]=1;
	vis[endx][endy]=2;
	while(!q.empty())
	{
		node top=q.front();
		q.pop();
		int x=top.x,y=top.y;
		for(int i=0;i<4;i++)
		{
			int nx=x+dx[i],ny=y+dy[i];
			if(nx<1||ny<1||nx>n||ny>m) continue;
			if(dis_to_tree[nx][ny]<dis) continue;
			if(!vis[nx][ny])
			{
				vis[nx][ny]=top.type;
				q.push({nx,ny,0,top.type});
			}
			else if(vis[nx][ny]!=top.type)
			{
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>mp[i][j];
			if(mp[i][j]=='V') startx=i,starty=j;
			if(mp[i][j]=='J') endx=i,endy=j;
		}
	}
	search1();
	if(startx==endx&&starty==endy)
	{
		cout<<dis_to_tree[startx][starty]<<endl;
		return 0;
	}
	int l=0,r=1000;
	while(l<r)
	{
		int mid=(l+r+1)>>1;
		if(solve(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l<<endl;
	return 0;
}
#题解
【题解】洛谷P7775
http://j27egu.github.io/2025/07/23/【题解】洛谷P7775/
作者
j27eGU
发布于
2025年7月23日
许可协议