P5474题解

silverleo · 2023-10-17 23:53:10 · 题解

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

思路：

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

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

复杂度

代码

#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;
}