AcWing 189. 乳草的入侵
原题链接
简单
作者:
Jackyc
,
2021-04-15 19:14:31
,
所有人可见
,
阅读 573
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
int n,m;
PII start;
const int N = 110;
char g[N][N];
int dis[N][N];
int res = -10;
int bfs(){
queue<PII> q;
memset(dis,-1,sizeof dis);
q.push(start);
dis[start.x][start.y] = 0; //赋初值!,否则从-1 加起
while(q.size()){
auto t = q.front();
q.pop(); //不要忘记弹出,否则死循环
for(int i = - 1; i <= 1; i ++) //八个方向,不用开方向数组
for(int j = -1; j <= 1; j ++){
int a = t.x + i,b = t.y + j;
if(a < 1 || a > n || b < 1 || b > m) continue; //注意修改 不是a < 0 ..
if(dis[a][b] != -1) continue;
if(g[a][b] == '*') continue;
dis[a][b] = dis[t.x][t.y] + 1;
res = max(res,dis[a][b]); //求解该题关键点,就是到达最后一块草地的距离就是答案
q.push({a,b});
}
}
return res;
}
int main(){
cin >> m >> n >> start.y >> start.x; //输入x1,y1是数学坐标系
start.x = n - start.x + 1; //修改得到代码坐标系,输出x2,y2,即y2 = x1, x2 = n - y1 + 1
for(int i = 1 ; i <= n ; i ++) //注意输入 横纵坐标从1开始!
cin >> (g[i] + 1);
cout << bfs() << endl;
return 0;
}
5,6行记下了!