刚学OI的蒟蒻萌新求助,不知道为啥会这么大。。。

回复帖子

@EmptySet 2019-08-14 21:20 回复

题目 乳草的入侵 乳草的入侵

题目描述

Farmer John一直努力让他的草地充满鲜美多汁的而又健康的牧草。可惜天不从人愿,他在植物大战人类中败下阵来。邪恶的乳草已经在他的农场的西北部份佔领了一片立足之地。 草地像往常一样,被分割成一个高度為Y(1 < = y < = 100), 宽度為X(1 < = x < = 100)的直角网格。(1,1)是左下角的格(也就是说坐标排布跟一般的X,Y坐标相同)。乳草一开始佔领了格(Mx,My)。每个星期,乳草传播到已被乳草佔领的格子四面八方的每一个没有很多石头的格(包括垂直与水平相邻的和对角线上相邻的格)。1周之后,这些新佔领的格又可以把乳草传播到更多的格裡面了。 Bessie想要在草地被乳草完全佔领之前尽可能的享用所有的牧草。她很好奇到底乳草要多久才能佔领整个草地。如果乳草在0时刻处於格(Mx,My),那麼在哪个时刻它们可以完全佔领入侵整片草地呢(对给定的数据总是会发生)? 草地由一个图片表示。" ." 表示草,而" *" 表示大石。

输入

  • 第一行: 四个由空格隔开的整数: X, Y, Mx, My
  • 第2到第Y+1行: 数据的第y+1行由X个字符(" ." 表示草地," *" 表示大石),描述草地的 第(Y+2-y)行。

输出

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

样例输入

4 3 1 1

....

..*.

.**.

样例输出

4

本蒟蒻的题解

#include<bits/stdc++.h>
using namespace std;
int head,tail,x,y,mx,my,ans,n[101][101],ax,ay,deep;
int mox[8]={1,0,1,-1,0,-1,1,-1};
int moy[8]={0,1,1,0,-1,-1,-1,1};
char m[101][101];
bool book[101][101];
bool judge(char m)
{
    if (m=='.') return false;
    return true;
}
void bfs()
{
    int sum=0;
    head=0;
    tail=1;
    ans=0;
    n[1][0]=mx;
    n[1][1]=my;
    n[1][2]=0;
    do
{
    head++;
    for(int i=0;i<=7;i++)
    {
    ax=n[head][0]+mox[i];
    ay=n[head][1]+moy[i];
    deep=n[head][2]+1;
   if((ax>0)&&
     (ax<=x)&&
     (ay>0)&&
     (ay<=y)&&
     (book[ax][ay]==false))
    {
        tail++;
        n[tail][0]=ax;
        n[tail][1]=ay;
        n[tail][2]=deep;
        book[ax][ay]=true;
    }   
    }
  ans++; 
  sum=0;
    for(int i=1;i<=x;i++)
     for(int j=1;j<=y;j++)
    {
      if(book[i][j]==true)
     {  
        sum++;
       if(sum==x*y)
       {
        printf("%d",&ans);
       exit(0);
        }
    }
    else break;
     }
   }
    while(head<tail);
}
int main()
{
    cin>>x>>y>>mx>>my;
    for(int i=1;i<=y;i++)
      for(int j=1;j<=x;j++)
      {
        scanf(" %c",&m[i][j]);
        if(m[i][j]=='*') 
         book[i][j]=true;
        else book[i][j]=false;
      }
    book[mx][my]=true;
    bfs();
}
@   吾皇 2019-08-14 21:41 回复 举报

@qwq_me 如果您的代码在bfs一块没有太大问题的话,就应该是判断草的多少上有误了,应为 if(sum+stone==x*y)

@   吾皇 2019-08-14 22:13 回复 举报
for(int i=1;i<=y;i++)
      for(int j=1;j<=x;j++)
      {
        scanf(" %c",&m[i][j]);
        if(m[i][j]=='*') 
         book[i][j]=true;
        else book[i][j]=false;
      }

不应该是

for(int i=1;i<=x;i++)
      for(int j=1;j<=y;j++)
      {
        scanf(" %c",&m[i][j]);
        if(m[i][j]=='*') 
         book[i][j]=true;
        else book[i][j]=false;
      }

吗?

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。