BNUOJ 1038 Flowers(BFS) - c++编程基础

Flowers

Time Limit: 1000ms Memory Limit: 65535KB 64-bit integer IO format: %lld Java class name: Main Prev Submit Status Statistics Discuss Next 春天到了,师大的园丁们又开始忙碌起来了.

京师广场上有一块空地,边界围成了一个多边形,内部被划分成一格一格的.园丁们想在这个多边形内的每一格内种植一些花.

现在请你帮忙计算一下一共最多可以种多少花.

广场用一个M*N的字符数组表示,.和*代表一个方格,其中*代表空地的边界,.是空格,只有边界内部的空格才能用于种花.
一个空格位于边界内部，当且仅当由该点出发只允许向上、下、左、右四个方向移动，最终都会遇到边界。

例如下面就是一个6*7的广场

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

种花方案如下(数字代表的地方)
.......
..***..
..*12*.
..*34*.
...**..
.......

Input

输入数据第一行是M和N(M和N不超过100),代表有广场的大小
接下来就是一个M*N的字符矩阵,是广场的表示

Output

对应于输入数据,输出一个整数,给出输入的情形能够种的花数目.

Sample Input

Sample Input1
6 7
.......
..***..
..*..*.
..*..*.
...**..
.......
Sample Input2
5 7
.......
..***..
..*.*..
..***..
.......

Sample Output

Sample Output1
4
Sample Output2
1

Source

第七届北京师范大学程序设计竞赛热身赛第四场

#include
  
   
#include
   
     #include
    
      using namespace std; const int N = 105 ; struct node { int x,y; }; char mapt[N][N]; int vist[N][N],n,m; int dir[4][2]={0,1,0,-1,1,0,-1,0}; int bfs(int x,int y) { queue
     
      q; node now,pre; int ans=1,flag=1; vist[x][y]=1; now.x=x; now.y=y; q.push(now); while(!q.empty()) { pre=q.front(); q.pop(); for(int e=0; e<4; e++) { now.x=pre.x+dir[e][0]; now.y=pre.y+dir[e][1]; if(now.x<0||now.x>=n||now.y<0||now.y>=m) { flag=0; continue; } if(!vist[now.x][now.y]&&mapt[now.x][now.y]=='.') { vist[now.x][now.y]=1; ans++; q.push(now); } } } if(flag==0) ans=0; return ans; } int main() { //int n,m; while(scanf(%d%d,&n,&m)>0) { for(int i=0; i
      
       ?