自动搬运

查看原文

来自洛谷，原作者为

	•́へ•́╬ Unsuccessful Leaving Something attempt

搬运于2025-08-24 22:45:24，当前版本为作者最后更新于2023-03-03 23:45:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

诈骗。所有人走的路径一定都是一样的。bfs 搜出来即可。

给人看的思路

首先，如果没有向上走，那么会向下走 $n-1$ 次。

考虑在整个过程中向上走了 $x$ 次。那么，就要额外向下走 $x$ 次，也就是一共向下走 $x+n-1$ 次。酱紫最后才能到达最后一行。

向左向右同理。

把向上和向左的次数加起来记作 $a$，统称【向回走】。

那么，会【向前走】 $n-1+m-1+a$ 次。

搜出使 $a$ 最小的路径。

code

#include<stdio.h>
#include<deque>
using namespace std;
inline char nc()
{
	static char buf[99999],*l,*r;
	return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
	char c=nc();for(;c<'0'||'9'<c;c=nc());
	for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,m,p,ans[2333][2333];long long ans1=1ll<<60,ans2;char s[2333][2333];
struct node
{
	int x,y,a;
	inline node(const int&x,const int&y,const int&a):x(x),y(y),a(a){}
};deque<node>q;
main()
{
	read(n);read(m);read(p);
	for(int i=0;i<n;++i)for(int j=0;j<m;s[i][j]^='X',ans[i][j++]=1<<30)
		for(;s[i][j]=nc(),(s[i][j]^'.')&&(s[i][j]^'X'););
	ans[0][0]=0;q.emplace_back(0,0,0);
	for(node i(0,0,0);q.size();)
	{
		i=q.front();q.pop_front();
		if(ans[i.x][i.y]^i.a)continue;
		if(i.x&&s[i.x-1][i.y]&&ans[i.x-1][i.y]>i.a+1)
			q.emplace_back(i.x-1,i.y,ans[i.x-1][i.y]=i.a+1);
		if(i.y&&s[i.x][i.y-1]&&ans[i.x][i.y-1]>i.a+1)
			q.emplace_back(i.x,i.y-1,ans[i.x][i.y-1]=i.a+1);
		if(i.x<n-1&&s[i.x+1][i.y]&&ans[i.x+1][i.y]>i.a)
			q.emplace_front(i.x+1,i.y,ans[i.x+1][i.y]=i.a);
		if(i.y<m-1&&s[i.x][i.y+1]&&ans[i.x][i.y+1]>i.a)
			q.emplace_front(i.x,i.y+1,ans[i.x][i.y+1]=i.a);
	}
	for(int x,y;p--;)
	{
		read(x);read(y);
		long long qwq=x*(long long)(n-1+m-1+ans[n-1][m-1])+
			y*(long long)(ans[n-1][m-1]);
		if(qwq<ans1)ans1=qwq,ans2=0;
		if(qwq==ans1)++ans2;
	}
	printf("%lld %lld",ans1,ans2);
}