自动搬运

查看原文

来自洛谷，原作者为

	silverleo **

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

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

以下是正文

一个容易实现的题解，不需要用到图。

思路：

• 对于能直接推走的车，推走之后剩下的局面一定比原始局面更优。
• 因为题目保证有解，所以不管推走几辆车，一定不会出现任何一辆车都无法推走的局面。

所以只需要不断的沿四周检查，把靠边的能推出的车子推出就可以了，直到车子全部推完。用两个双向链表保存 4 个方向的车辆顺序，推出车子也就是在链表中删除节点。

复杂度

$O(n \times m)$

代码

#include<bits/stdc++.h>
using namespace std;

int n,m,cnt;
char a[2005][2005];
int L[2005][2005],R[2005][2005],U[2005][2005],D[2005][2005];

void del(int i,int j,bool print){
	//双向链表中删除节点
	L[i][R[i][j]]=L[i][j];
	R[i][L[i][j]]=R[i][j];
	U[D[i][j]][j]=U[i][j];
	D[U[i][j]][j]=D[i][j];
	cnt--;
	if(print)cout<<"("<<i-1<<","<<j-1<<")"<<endl;
}

int main(){
	cin>>n>>m;
	cnt=n*m;
	for(int i =0;i<=n+1;i++){
		for(int j=0;j<=m+1;j++){
			L[i][j] = j-1;
			R[i][j] = j+1;
			U[i][j] = i-1;
			D[i][j] = i+1;
		}
	}
	for(int i =1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='.')del(i,j,false);
		}
	}
	while(cnt>0){
		for(int i =1;i<=n;i++){
			while(a[i][R[i][0]]=='W')del(i,R[i][0],true);
			while(a[i][L[i][m+1]]=='E')del(i,L[i][m+1],true);
		}
		for(int i =1;i<=m;i++){			
			while(a[D[0][i]][i]=='N')del(D[0][i],i,true);
			while(a[U[n+1][i]][i]=='S')del(U[n+1][i],i,true);
		}
	}
	return 0;
}