目 录
- 题面
- 题目描述
- 输入格式
- 输出格式
- 输入输出样例
- 输入
- 输出
- 题目分析
- Code
题面
题目传送门
题目描述
Farmer John一直努力让他的草地充满鲜美多汁的而又健康的牧草。可惜天不从人愿，他在植物大战人类中败下阵来。邪恶的乳草已经在他的农场的西北部份占领了一片立足之地。
草地像往常一样，被分割成一个高度为Y(1 <= Y <= 100), 宽度为X(1 <= X <= 100)的直角网格。(1,1)是左下角的格（也就是说坐标排布跟一般的X,Y坐标相同）。乳草一开始占领了格(Mx,My)。每个星期，乳草传播到已被乳草占领的格子四面八方的每一个没有很多石头的格（包括垂直与水平相邻的和对角在线相邻的格）。1周之后，这些新占领的格又可以把乳草传播到更多的格里面了。
Bessie想要在草地被乳草完全占领之前尽可能的享用所有的牧草。她很好奇到底乳草要多久才能占领整个草地。如果乳草在0时刻处于格(Mx,My)，那么会在哪个时刻它们可以完全占领入侵整片草地呢？对给定的数据总是会发生。
输入格式
-
Line 1: Four space-separated integers: X, Y, Mx, and My
-
Lines 2…Y+1: Line y+1 describes row (Y+2-y) of the field with X characters (’.’ for grass and ‘*’ for a boulder)
输出格式
- Line 1: A single integer that is the week number when the milkweed takes over the last remaining non-boulder square of the pasture.
输入输出样例
输入
4 3 1 1
....
..*.
.**.
输出
4
题目分析
(一看就知道是USACO的题目）
对于这种题目，一看就知道是一个搜索。
bfs一遍就完事了。
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct node{int u,v,w;
};
int dx[8]={1,1,1,-1,-1,-1,0,0};
int dy[8]={1,0,-1,1,0,-1,1,-1};
char a[105][105];
int g[105][105],n,m,mx,my,ans=0;
void bfs(int x,int y){queue<node> q;q.push((node){x,y,0});g[x][y]=1;while(!q.empty()){node h=q.front();q.pop();ans=h.w;for(int i=0;i<8;i++){int fx=h.u+dx[i];int fy=h.v+dy[i];if(a[fx][fy]=='.'&&g[fx][fy]==0){g[fx][fy]=1;q.push((node){fx,fy,ans+1});}}}
}
int main(){//freopen("1.in","r",stdin);int i,j;memset(g,0,sizeof(g));scanf("%d%d%d%d",&m,&n,&my,&mx);for(i=n;i>=1;i--)for(j=1;j<=m;j++)cin>>a[i][j];bfs(mx,my);printf("%d",ans);return 0;
}