建站实战干货

[https://www.luogu.com.cn/problem/AT_abc427_e](暴力+STL）

题意：

给出二维矩阵：T在的位置以及垃圾#在的位置，每次可以使所有#向上/下/左/右移动一次，求使得垃圾不到T而全部被移除的最小操作次数

思路：

用一个set存所有#现在的位置，BFS每次枚举4个方向，map去重状态

int n,m;
queue<pair<set<pii>,int>>q;
pii sx;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
map<set<pii>,int>vis;
void solve(){cin>>n>>m;set<pii>st;rep(i,1,n){rep(j,1,m){char k;cin>>k;if(k=='#')st.insert({i,j});else if(k=='T')sx={i,j};}}q.push({st,0});while(q.size()){auto[Set,step]=q.front();q.pop();if(vis.count(Set))continue;vis[Set]=1;if(Set.size()==0){cout<<step<<endl;return;}for(int i=0;i<4;i++){set<pii>newset;int ok=1;for(auto[x,y]:Set){int nx=x+dx[i],ny=y+dy[i];if((pii){nx,ny}==sx){ok=0;break;}if(nx<1||nx>n||ny<1||ny>m)continue;newset.insert({nx,ny});}if(ok)q.push({newset,step+1});}}cout<<-1<<endl;
}