题目描述

You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black. HW characters from A11 to AHW represent the colors of the squares. Aij is # if the square at the i-th row from the top and the j-th column from the left is black, and Aij is . if that square is white.

We will repeatedly perform the following operation until all the squares are black:

Every white square that shares a side with a black square, becomes black.

Find the number of operations that will be performed. The initial grid has at least one black square.

Constraints

·1≤H,W≤1000

·Aij is # or ..

·The given grid has at least one black square.

输入

Input is given from Standard Input in the following format:

H W

A11A12...A1W

:

AH1AH2...AHW

输出

Print the number of operations that will be performed.

样例输入

复制样例数据

3 3....#....

样例输出

2

提示

After one operation, all but the corners of the grid will be black. After one more operation, all the squares will be black.

就不翻译了

思路：广度优先搜索 模板题

自己写的代码：

1 #include
      
        2 using namespace std; 3 typedef long long ll; 4 int vis[1005][1005]; 5 char arr[1005][1005]; 6 int main(){ 7    int n,m;cin>>n>>m; 8    for(int i=1;i<=n;i++){ 9     scanf("%s",arr[i]+1);10    }11    memset(vis,-1,sizeof(vis));12    typedef pair
       
        P;13    queue
        
que;14    for(int i=1;i<=n;i++){15     for(int j=1;j<=m;j++){16         if(arr[i][j]=='#') {17                 vis[i][j]=0;18                 que.push(P(i,j));19         }20     }21    }22    int maxx=0;23    while(!que.empty()){24     P p=que.front();que.pop();25     if(p.first-1>0&&vis[p.first-1][p.second]==-1){26         vis[p.first-1][p.second]=vis[p.first][p.second]+1;27         que.push(P(p.first-1,p.second));28         maxx=max(maxx,vis[p.first][p.second]+1);29     }30     if(p.first+1<=n&&vis[p.first+1][p.second]==-1){31         vis[p.first+1][p.second]=vis[p.first][p.second]+1;32         que.push(P(p.first+1,p.second));33         maxx=max(maxx,vis[p.first][p.second]+1);34     }35     if(p.second-1>0&&vis[p.first][p.second-1]==-1){36            vis[p.first][p.second-1]=vis[p.first][p.second]+1;37         que.push(P(p.first,p.second-1));38         maxx=max(maxx,vis[p.first][p.second]+1);39     }40     if(p.second+1<=m&&vis[p.first][p.second+1]==-1){41            vis[p.first][p.second+1]=vis[p.first][p.second]+1;42         que.push(P(p.first,p.second+1));43         maxx=max(maxx,vis[p.first][p.second]+1);44     }45    }46    cout<
         
          <
         
       
      

大神写的代码：

1 #include
      
        2 using namespace std; 3 const int maxn=1e5+5; 4 const int dx[]={
    1,-1,0,0}; 5 const int dy[]={
    0,0,1,-1}; 6  7 int n,m,ans; 8 char s[1111][1111]; 9 struct node { int x,y,step; };10 queue
       
         que;11 void bfs() {12     while (!que.empty()) {13         node now=que.front(); que.pop();14         ans=max(ans,now.step);15         for (int i=0;i<4;i++) {16             node nex=node{now.x+dx[i],now.y+dy[i],now.step+1};17             if (s[ nex.x ][ nex.y ]=='.') {18                 s[ nex.x ][ nex.y ]='#';19                 que.push(nex);20             }21         }22     }23 }24 int main () {25     scanf("%d%d",&n,&m);26     for (int i=1;i<=n;i++)27         for (int j=1;j<=m;j++) {28             scanf(" %c",&s[i][j]);29             if (s[i][j]=='#')30                 que.push(node{i,j,0});31         }32     bfs();33     printf("%d\n",ans);34     return 0;35 }
       
      

总结：刚开始的时候竟然往dfs上面想了，看来是好久没见bfs的题了，都不会做了。另外代码跟神犇写的差距太大了，要好好学习别人的代码呀。

　　　　　蒟蒻一枚；