记录编号	556992	评测结果	WAAAAAAAAWA
题目名称	[USACO Oct09] 乳草的入侵	最终得分	81
用户昵称	增强型图元文件	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2020-11-01 14:30:36	内存使用	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<=m&&y>=1&&y<=n&&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=m;i>=1;i--){
    		for(int j=1;j<=n;j++){
    			cin>>s[i][j];
    			if(s[i][j]=='.'){
    				cnt++;
    			}
    		} 
    	}
    	cout<<bfs(mx,my);
    	return 0;
    }