AtCoder ABC 213 E Stronger Takahashi (01BFS)
AtCoder ABC 213 E Stronger Takahashi (01BFS)
题目链接:E Stronger Takahashi
题目大意:
给出一张 \(n*m\) 的地图,从 \((1,1)\) 走到 \((n,m)\) ,只能走在 .
上不能走在 #
上,每次可以消掉 \(2×2\) 的 #
,求最少消掉几次才能到终点。
思路解析:
首先我们很直观的发现,对于每一次爆破,我们都可以到达如下的点
(*
代表此处爆破由#
变为*
>
\(.\ ***\ .\)
\(*****\)
\(**T**\)
\(*****\)
\(.\ ***\ .\)
所以我们可以使用 \(01BFS\) 来做这道题,我们优先进行代价为 \(0\) 的点的 \(bfs\) ,把它放在队头,而代价为 \(1\) 的点放在队尾,这样我们就可以优先处理代价小的路径,从而实现对问题的求解。
AC代码:
#include
using namespace std;
typedef pair pii;
typedef long long ll;
const int maxn=505;
int n,m,dis[maxn][maxn];
int vis[maxn][maxn];
char a[maxn][maxn];
dequeq;
int dx[20]={0,0,1,-1,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2};
int dy[20]={-1,1,0,0,-1,0,1,-2,-1,1,2,-2,2,-2,-1,1,2,-1,0,1};
int check(int x,int y){
if(x<1||x>n||y<1||y>m)return 1;
return 0;
}
void bfs(){
q.push_back(make_pair(1,1));
memset(dis,0x3f,sizeof dis);
dis[1][1]=0;
while(q.size()){
pii top=q.front();
q.pop_front();
int x=top.first,y=top.second;
if(vis[x][y])continue;
vis[x][y]=1;
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(check(xx,yy)||a[xx][yy]=='#')continue;
dis[xx][yy]=min(dis[xx][yy],dis[x][y]);
q.push_front(make_pair(xx,yy));
}
for(int i=0;i<20;i++){
int xx=x+dx[i],yy=y+dy[i];
if(check(xx,yy))continue;
dis[xx][yy]=min(dis[xx][yy],dis[x][y]+1);
q.push_back(make_pair(xx,yy));
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
bfs();
cout<