题目描述
AcWing 189. 乳草的入侵
代码虽然精简,但不难理解
难理解的地方,都解释了
算法1
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=110;
char g[N][N];
int dt[]={-1,0,1,1,1,0,-1,-1,-1,0}; //(dt[i],dt[i+2])就是跳的位置,因为转2次向,xy互换
int n,m,start,cnt;
bool check(int x,int y){
return x>=0 && x<n && y>=0 && y<m && g[x][y]!='*';
}
int bfs(){
queue<int> q;
q.push(start),q.push(-1); //-1标记一轮结束
g[start>>8][start&255]='*';
int dist=1;
while(q.size()){
int t=q.front();
q.pop();
if(t==-1) dist++, q.push(t);
int x=t>>8, y=t&255;
for(int i=0;i<8;i++){
int a=x+dt[i], b=y+dt[i+2];
if(!check(a,b))continue;
if(!--cnt)return dist;
g[a][b]='*'; //复用g
q.push((a<<8)+b);
}
}
}
int main(){
int x,y;
cin>>m>>n>>y>>x;
x--,y--;
start=(x<<8)+y;
for(int i=n-1;i>=0;i--){
cin>>g[i];
for(int j=0;j<m;j++)
cnt+=(g[i][j]=='.');
}
if(g[x][y]=='.')cnt--;
cout<<bfs()<<endl;
return 0;
}