自动搬运

查看原文

来自洛谷，原作者为

	O2人 无敌仙王，游戏人间。

搬运于2025-08-24 22:06:37，当前版本为作者最后更新于2019-12-08 16:24:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我发现，我现在在你谷发声（影响力大的）的唯一方式只有发题解了。

这是我初中三年第二次被你谷禁言，在一年的沉寂之后，我又在你谷上发声了，然而好景不长，我又被禁言了。

好了不扯了，看看这题吧。

因为不可能有两个横着的管子插在同一行，所以这题就很好模拟了。

步骤：

1.我们先暴力找到第一个箱子。

2.然后再从下往上枚举水位，一旦发现这一行有管子连着，就马上顺这管子下去,到达箱子x。

3.对x重复2操作

4.如果没管子了，就输出此时编号

所以肯定DFS

Code:

#include <bits/stdc++.h>
using namespace std;
int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-f;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();
	return ret*f;
}
const int maxn=1005,flg[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int n,m;
char A[maxn][maxn];
void DFS(int u,int x,int y){
	int L=0,H=0;
	while (A[x][y]!='+') y--;
	while (A[x+L+1][y]!='+') ++L;L+=2;
	while (A[x][y+H+1]!='+') ++H;H+=2;//算箱子宽度和高度
	for (int i=x;i<=x+L-1&&!u;i++)
	for (int j=y;j<=y+H-1&&!u;j++)
	if (A[i][j]>='0'&&A[i][j]<='9'){//找编号
		char ch=A[i][j];
		while (ch>='0'&&ch<='9') u=(u<<3)+(u<<1)+ch-'0',ch=A[i][++j];//类似快读的操作
		break;
	}
	for (int i=x+L-2;i>=x-1;i--)//枚举水位，并遍历
	if (A[i][y-1]=='-'||A[i][y+H]=='-'){
		int nx=i,ny,f;//f是方向，0，1，2，3具体代表什么方向看flg数组
		if (A[i][y-1]=='-') ny=y-1,f=3;
		else ny=y+H,f=1;
		while (true){
			nx+=flg[f][0],ny+=flg[f][1];
			if (A[nx][ny]=='+'){
				if ((f==0||f==2)&&A[nx][ny-1]!='.') f=3;else
				if ((f==0||f==2)&&A[nx][ny+1]!='.') f=1;else
				if ((f==1||f==3)&&A[nx+1][ny]!='.') f=2;//判断管子是否换方向
			}else
			if (A[nx-flg[f][0]][ny-flg[f][1]]=='|'&&A[nx][ny]=='-') break;//判断是否走到水箱上了
		}
		DFS(0,nx,ny);//继续走
	}
	printf("%d\n",u);
}
int main(){
	n=read(),m=read();
	for (int i=1;i<=n;i++) scanf("%s",A[i]+1);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
	if (A[i][j]=='+'){DFS(1,i,j);return 0;}//第一个箱子肯定在最上面，因为'+'上不能插管子
	return 0;
}