记录编号	557001	评测结果	AAWWWWAAWWA
题目名称	394.[USACO Oct09] 乳草的入侵	最终得分	45
用户昵称	增强型图元文件	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2020-11-01 15:00:44	内存使用	0.00 MiB

    #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&&y>=1&&y<=m){
    		if(s[x][y]=='.')
    			return true;
    		else return false;
    	}else{
    		return false;
    	}
    }
    void print(){
    	for(int i=1;i<=n;i++){
    	for(int j=1;j<=m;j++){
    		cout<<s[i][j];
    	}
    	cout<<endl;
    }
    }
    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;
    	queue<pair<int,int> > q;
    	q.push(make_pair(mx,my));
    	int nt=0;
    	nt++;
    	s[mx][my]='M';
    	while(!q.empty()){
    		pair<int,int> now=q.front();
    		q.pop();
    		//cout<<day[now.first][now.second]<<endl;
    		//print();
    		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)){
    				day[next.first][next.second]=day[now.first][now.second]+1;
    				q.push(next);
    				nt++;
    				s[next.first][next.second]='M';
    				if(nt==cnt){
    					return day[next.first][next.second];
    				}
    			}
    		}
    	}
    	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;
    }