Store-keeper解题报告
题目描述
题目传送门
大意：给定一个箱子和指定要推到的位置，其中路径中有障碍物，最小化推动次数。
解法
首先矩阵中走最少步数我们很容易想到用dp解，这题有用信息是人和箱子的位置。
最朴素的状态描述
很明显有冗余状态，会
我们可以观察到人的具体位置是不重要的，只要关心他在箱子的上下左右的相对位置即可。
于是有状态描述
我们发现对于一个箱子如果人要切换到箱子的另一个方位是不一定可行的，这就是转移的难点所在。
难点：无法确定对于一个位置
通过观察可以猜想，因为不能到达只可能是被箱子挡住了，所以问题变为两个点之间删去一个点还能到达要满足什么充要条件。
矩阵中的 dp 问题通常需要构图，利用一些图上算法处理。
这让我们想到了图论中关于点双连通分量的一个结论：点双连通分量中，任意两点存在没有相同点的路径。
于是我们猜想如果两点在同一点双连通分量中则可以互相到达，两点不在同一点双连通分量中则不能。
证明：我们考虑
- 假设
u,v 在同一点双连通分量中显然可以。 - 假设
u,v 不在同一点双连通分量中，若u,v 可以互相到达，则u,v 中一定存在一条不经过t 的路径。那么如果t 可以经过u,v 之间又会存在一条路径可互相到达，那么u,v 一定在一个点双连通分量中，与假设矛盾。
证毕。
算法流程：
- bfs找初始状态。
- tarjan预处理每个哪些点双连通分量中（注意一条边只属于一个点双连通分量，而一个点可能却属于多个多个点双连通分量，注意要记录边在哪个分量中，而不是点）。
- 利用01bfs求解dp。
再说一下可以用 01bfs 求解是因为只有两种转移方式一种换方向花费为
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<utility>
#include<map>
#include<iostream>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
const int maxn=100*100+10;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
int n,m,a[110][110],M,P,K,low[maxn],dep[maxn],val[maxn],nnum,rt,dsl,ans=-1,dp[110][110][4];
char aa[110][110];
bool vis[110][110][4],can[110][110],vv[maxn],ve[maxn],vb[110][110];
vector<int>vec;
stack<int>sta;
map<int,pair<int,int> >ed;
struct node{
int x,y,z;
node(int x_,int y_,int z_){
x=x_,y=y_,z=z_;
}
node(){}
}f[maxn];
struct edge{
int to,nxt,num;
}e[maxn<<2];
int head[maxn],cnt=1;
void add(int u,int v,int num){
e[cnt].to=v,e[cnt].nxt=head[u],e[cnt].num=num,head[u]=cnt++;
}
queue<node>q;
deque<node>qq;
int id(int x,int y){
if(x<1||x>n||y<1||y>m) return -1;
return (x-1)*m+y;
}
void fd(){
q.push(node(f[M].x,f[M].y,f[M].z));
vb[f[M].x][f[M].y]=1;
while(!q.empty()){
node now=q.front();
q.pop();
can[now.x][now.y]=1;
for(int i=0;i<=3;i++){
int nx=now.x+dx[i],ny=now.y+dy[i];
if(nx>n||nx<0||ny>m||ny<0||aa[nx][ny]=='S'||can[nx][ny]||aa[nx][ny]=='P'||aa[nx][ny]==0||vb[nx][ny]) continue;
vb[nx][ny]=1;
q.push(node(nx,ny,-1));
}
}
}
void dfs(int u,int d){
vv[u]=1,low[u]=dep[u]=d;
bool flag=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!ve[e[i].num]) sta.push(e[i].num),ve[e[i].num]=1;
if(!vv[v]){
dfs(v,d+1);
low[u]=min(low[u],low[v]);
if(low[v]>=dep[u]){
dsl++;
while(sta.top()!=e[i].num)
val[sta.top()]=dsl,sta.pop();
val[e[i].num]=dsl,sta.pop();
}
}
else if(dep[v]<dep[u]-1)
low[u]=min(low[u],dep[v]);
}
}
bool isin(int x,int y){
if(x==-1||y==-1) return 0;
for(int i=head[x];i;i=e[i].nxt)
for(int j=head[y];j;j=e[j].nxt){
if(val[e[i].num]==val[e[j].num]) return 1;
}
return 0;
}
void bfs(){
int sx=f[P].x,sy=f[P].y;
memset(dp,0x3f,sizeof(dp));
if(can[sx-1][sy]) qq.push_front(node(sx,sy,0)),dp[sx][sy][0]=0,vis[sx][sy][0]=1;
if(can[sx+1][sy]) qq.push_front(node(sx,sy,1)),dp[sx][sy][1]=0,vis[sx][sy][1]=1;
if(can[sx][sy-1]) qq.push_front(node(sx,sy,2)),dp[sx][sy][2]=0,vis[sx][sy][2]=1;
if(can[sx][sy+1]) qq.push_front(node(sx,sy,3)),dp[sx][sy][3]=0,vis[sx][sy][3]=1;
while(!qq.empty()){
node now=qq.front();
qq.pop_front();
int x=now.x,y=now.y,z=now.z;
if(now.x==f[K].x&&y==f[K].y){
ans=dp[x][y][z];
return;
}
if(z==0){
if(aa[x+1][y]!=0&&aa[x+1][y]!='S'&&!vis[x+1][y][z])
vis[x+1][y][0]=1,dp[x+1][y][0]=dp[x][y][0]+1,qq.push_back(node(x+1,y,z));
if(!vis[x][y][1]&&isin(id(x-1,y),id(x+1,y)))
vis[x][y][1]=1,dp[x][y][1]=dp[x][y][0],qq.push_front(node(x,y,1));
if(!vis[x][y][2]&&isin(id(x-1,y),id(x,y-1)))
vis[x][y][2]=1,dp[x][y][2]=dp[x][y][0],qq.push_front(node(x,y,2));
if(!vis[x][y][3]&&isin(id(x-1,y),id(x,y+1)))
vis[x][y][3]=1,dp[x][y][3]=dp[x][y][0],qq.push_front(node(x,y,3));
}
if(z==1){
if(aa[x-1][y]!=0&&aa[x-1][y]!='S'&&!vis[x-1][y][z])
vis[x-1][y][1]=1,dp[x-1][y][1]=dp[x][y][1]+1,qq.push_back(node(x-1,y,z));
if(!vis[x][y][0]&&isin(id(x+1,y),id(x-1,y)))
vis[x][y][0]=1,dp[x][y][0]=dp[x][y][1],qq.push_front(node(x,y,0));
if(!vis[x][y][2]&&isin(id(x+1,y),id(x,y-1)))
vis[x][y][2]=1,dp[x][y][2]=dp[x][y][1],qq.push_front(node(x,y,2));
if(!vis[x][y][3]&&isin(id(x+1,y),id(x,y+1)))
vis[x][y][3]=1,dp[x][y][3]=dp[x][y][1],qq.push_front(node(x,y,3));
}
if(z==2){
if(aa[x][y+1]!=0&&aa[x][y+1]!='S'&&!vis[x][y+1][z])
vis[x][y+1][2]=1,dp[x][y+1][2]=dp[x][y][2]+1,qq.push_back(node(x,y+1,z));
if(!vis[x][y][0]&&isin(id(x,y-1),id(x-1,y)))
vis[x][y][0]=1,dp[x][y][0]=dp[x][y][2],qq.push_front(node(x,y,0));
if(!vis[x][y][1]&&isin(id(x,y-1),id(x+1,y)))
vis[x][y][1]=1,dp[x][y][1]=dp[x][y][2],qq.push_front(node(x,y,1));
if(!vis[x][y][3]&&isin(id(x,y-1),id(x,y+1)))
vis[x][y][3]=1,dp[x][y][3]=dp[x][y][2],qq.push_front(node(x,y,3));
}
if(z==3){
if(aa[x][y-1]!=0&&aa[x][y-1]!='S'&&!vis[x][y-1][z])
vis[x][y-1][3]=1,dp[x][y-1][3]=dp[x][y][3]+1,qq.push_back(node(x,y-1,z));
if(!vis[x][y][0]&&isin(id(x,y+1),id(x-1,y)))
vis[x][y][0]=1,dp[x][y][0]=dp[x][y][3],qq.push_front(node(x,y,0));
if(!vis[x][y][1]&&isin(id(x,y+1),id(x+1,y)))
vis[x][y][1]=1,dp[x][y][1]=dp[x][y][3],qq.push_front(node(x,y,1));
if(!vis[x][y][2]&&isin(id(x,y+1),id(x,y-1)))
vis[x][y][2]=1,dp[x][y][2]=dp[x][y][3],qq.push_front(node(x,y,2));
}
}
}
int main(){
scanf("%d%d",&n,&m);
memset(aa,0,sizeof(aa));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>aa[i][j];
f[id(i,j)].x=i,f[id(i,j)].y=j;
if(aa[i][j]!='S'){
vec.push_back(id(i,j));
if(aa[i-1][j]!=0&&aa[i-1][j]!='S') nnum++,add(id(i,j),id(i-1,j),nnum),add(id(i-1,j),id(i,j),nnum);
if(aa[i][j-1]!=0&&aa[i][j-1]!='S') nnum++,add(id(i,j),id(i,j-1),nnum),add(id(i,j-1),id(i,j),nnum);
}
if(aa[i][j]=='M') M=id(i,j);
if(aa[i][j]=='P') P=id(i,j);
if(aa[i][j]=='K') K=id(i,j);
}
fd();
for(int i=0;i<vec.size();i++)
if(!vv[vec[i]])
rt=vec[i],dfs(vec[i],0);
bfs();
if(ans==-1) printf("NO");
else printf("%d",ans);
return 0;
}