比赛 20201031 评测结果 AATWTWTAWWT
题目名称 乳草的入侵 最终得分 27
用户昵称 增强型图元文件 运行时间 4.000 s
代码语言 C++ 内存使用 1.27 MiB
提交时间 2020-10-31 08:56:06
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
int m,n,mx,my;
char s[110][110]; 
int mv[8][2]={{0,1},{1,0},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
int cnt=0;
bool check(int x,int y){
	if(x>=1&&x<=n&&x>=1&&x<=m&&s[x][y]!='*'){
		return true;
	}else{
		return false;
	}
}
int bfs(int x,int y){
	int day[110][110];
	bool vis[110][110]={0};
	/*
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			day[i][j]=-1;
		} 
	}
	*/
	day[mx][my]=0;
	vis[mx][my]=1;
	queue<pair<int,int> > q;
	q.push(make_pair(mx,my));
	int nt=0;
	while(q.size()){
		pair<int,int> now=q.front();
		q.pop();
		if(s[now.first][now.second]=='.'){
			nt++;
		}
		if(nt==cnt){
			return day[now.first][now.second];
		}
		for(int i=0;i<8;i++){
			pair<int,int> next=make_pair(now.first+mv[i][0],now.second+mv[i][1]);
			if(check(next.first,next.second)&&!vis[next.first][next.second]){
				day[next.first][next.second]=day[now.first][now.second]+1;
				q.push(next);
				vis[next.first][next.second]=1;
			}
		}
	}
	return -1;
}
int main(int argc, char** argv) {
	freopen("milkweed.in","r",stdin);
	freopen("milkweed.out","w",stdout);
	cin>>m>>n>>mx>>my;
	for(int i=n;i>=1;i--){
		for(int j=1;j<=m;j++){
			cin>>s[i][j];
			if(s[i][j]=='.'){
				cnt++;
			}
		} 
	}
	cout<<bfs(mx,my);
	return 0;
}