比赛 20201031 评测结果 AAWWWWAAWWA
题目名称 乳草的入侵 最终得分 45
用户昵称 tat 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2020-10-31 13:20:24
显示代码纯文本
#include <bits/stdc++.h>
using namespace std; 
char ma[101][101];
int czx[8]={0,0,-1,1,1,-1,1,-1};
int czy[8]={1,-1,0,0,1,-1,-1,1};
int v[101][101]={0},ans[101][101];
int n,m,sx,sy;
int main(int argc, char** argv) {
	freopen("milkweed.in","r",stdin);
	freopen("milkweed.out","w",stdout);
    cin>>m>>n>>sx>>sy;
    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
        	cin>>ma[i][j];
        	ans[i][j]=10000000;
		}
	}
	//bfs
	queue<int> x;
	queue<int> y;
	x.push(sx);
	y.push(sy);
	ans[sx][sy]=0;
	while(!x.empty()){
		int nx,ny;
		nx=x.front();
		ny=y.front();
		x.pop();
		y.pop();
		for(int i=0;i<=7;i++){
			int xx=nx+czx[i],yy=ny+czy[i];
			if((xx>0)&&(xx<=n)&&(yy>0)&&(yy<=m)&&(ma[xx][yy]!='*')&&(v[xx][yy]==0)){
				v[xx][yy]=1;
				x.push(xx);
				y.push(yy);
				ans[xx][yy]=ans[nx][ny]+1;
			}
		}
	}
	int minn=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(ma[i][j]!='*')minn=max(ans[i][j],minn);
		}
	}
	if(minn>10000){
		cout<<-1<<endl;
	}
	else cout<<minn<<endl;
	return 0;
}
/*
..**
.*.*
.*.*
....
*/