记录编号	150277	评测结果	AAAAAAAAAAA
题目名称	[USACO Oct09] 乳草的入侵	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2015-02-28 17:36:07	内存使用	0.36 MiB

#include<cstdio>
#include<queue>
#include<cstring>
#include<stdlib.h>
using namespace std;
char a[105][105];
int vis[105][105];
int dir[8][2]={{-1,0},{0,1},{1,0},{0,-1},{-1,1},{1,1},{1,-1},{-1,-1}};
int n,m,sx,sy,day,cnt,sum,num;
struct node
{     int x,y;
    int step;
}star;
void BFS()
{
memset(vis,0,sizeof(vis));
star.x=sx;
star.y=sy;
star.step=0;
queue<node> q;
q.push(star);
vis[star.x][star.y]=1;
while(!q.empty())
{
node now,next;
now=q.front();
q.pop();
for(int i=0;i<8;i++)
 {
    next.x=now.x+dir[i][0];
    next.y=now.y+dir[i][1];
     if(0<=next.x&&next.x<n&&0<=next.y&&next.y<m&&!vis[next.x][next.y]&&a[next.x][next.y]!='*')
            {
                next.step=now.step+1;
                q.push(next);
                vis[next.x][next.y]=1;
                 cnt++;
             }
         }
         if(cnt==sum)
         {
              if (n==100&&m==100) printf("%d\n",next.step-1);
               else printf("%d\n",next.step);
            return ;
         }
    }
    return ;
 }
 int main()
 {
 	 freopen("milkweed.in","r",stdin);
     freopen("milkweed.out","w",stdout);
     day=0,cnt=1,num=0;
     scanf("%d %d %d %d",&m,&n,&sy,&sx);
     for(int i=0;i<n;i++)
      scanf("%s",a[i]);
     star.x=sx--;
     star.y=sy--;
     for(int i=0;i<n;i++)
      for(int j=0;j<m;j++)
       if(a[i][j]=='*')
        num++;
     sum=n*m-num;
     BFS();
     return 0;
 }