[TYVJ] P1030 乳草的入侵

乳草的入侵

背景 Background

USACO OCT09 6TH

描述 Description

Farmer John一直努力让他的草地充满鲜美多汁的而又健康的牧草。可惜天不从人愿，他在植物大战人类中败下阵来。邪恶的乳草已经在他的农场的西北部份佔领了一片立足之地。

草地像往常一样，被分割成一个高度為Y(1 <= y <= 100), 宽度為X(1 <= x <= 100)的直角网格。(1,1)是左下角的格（也就是说坐标排布跟一般的X,Y坐标相同）。乳草一开始佔领了格(Mx,My)。每个星期，乳草传播到已被乳草佔领的格子四面八方的每一个没有很多石头的格（包括垂直与水平相邻的和对角线上相邻的格）。1周之后，这些新佔领的格又可以把乳草传播到更多的格裡面了。

Bessie想要在草地被乳草完全佔领之前尽可能的享用所有的牧草。她很好奇到底乳草要多久才能佔领整个草地。如果乳草在0时刻处於格(Mx,My)，那麼还在那个时刻它们可以完全佔领入侵整片草地呢（对给定的数据总是会发生）？

草地由一个图片表示。"."表示草，而"*"表示大石。比如这个X=4, Y=3的例子。

     ....
     ..*.
     .**.

如果乳草一开始在左下角（第1排，第1列），那麼草地的地图将会以如下态势发展：

      ....  ....  MMM.  MMMM  MMMM
      ..*.  MM*.  MM*.  MM*M  MM*M
      M**.  M**.  M**.  M**.  M**M
星期数  0     1     2     3     4

乳草会在4星期后佔领整片土地。

输入格式 InputFormat

* 第一行: 四个由空格隔开的整数: X, Y, Mx, My

* 第2到第Y+1行: 数据的第y+1行由X个字符（"."表示草地，"*"表示大石），描述草地的
第(Y+2-y)行。

输出格式 OutputFormat

* 第一行: 一个单独的整数表示最后一个不是大石块的格子被乳草佔领的星期数。

样例输入 SampleInput [复制数据]

4 3 1 1
....
..*.
.**.

样例输出 SampleOutput [复制数据]

题解：广度优先搜索模板题

代码：

 1 #include<stdio.h>
 2 #include<stdbool.h>
 3 #include<string.h>
 4 int i,j,n,m,mx,my,maxi=-1,
 5     dx[9]={0,0,0,1,-1,1,-1,1,-1},
 6     dy[9]={0,1,-1,0,0,1,-1,-1,1},
 7     q[100000][2],
 8     dist[110][110];
 9 bool can[110][110];
10 char a[200];
11 
12 void
13 pre(void)
14 {
15     memset(dist,0,sizeof(dist));
16     memset(q,0,sizeof(q));
17     
18 }
19 
20 int
21 init(void)
22 {
23     scanf("%d%d%d%d
",&n,&m,&my,&mx);
24     for (i=1;i<=m;i++)
25     { 
26         scanf("%s",a);
27         for(j=0;j<=strlen(a);j++)
28         if (a[j]=='.') can[i][j+1]=true;
29     }
30     return 0;
31 }
32 
33 int 
34 bfs(void)
35 {
36     int i,x1,y1,xx,yy,head,tail;
37     head=0;tail=1;
38     q[1][0]=mx;q[1][1]=my;
39     can[mx][my]=false;
40     while (head!=tail)
41     {
42         head=head%100000+1;
43         x1=q[head][0];y1=q[head][1];
44         for(i=1;i<=8;i++)
45         {
46             xx=x1+dx[i];
47             yy=y1+dy[i];
48            if (can[xx][yy])
49            {
50               tail=tail%100000+1;
51               q[tail][0]=xx;
52               q[tail][1]=yy;
53               dist[xx][yy]=dist[x1][y1]+1;
54               can[xx][yy]=false;
55             }
56         }
57     }
58     return 0;
59 }
60 
61 int
62 main(void)
63 {
64     pre();
65     init();
66     bfs();
67     
68     for(i=1;i<=m;i++)
69     {
70         for(j=1;j<=n;j++)
71         if (dist[i][j]>maxi) maxi=dist[i][j];
72     }
73           printf("%d
",maxi);
74     return 0;
75 }