---
title: NEU1682 全球变暖（bfs+dfs）
layout: post
permalink: /archives/311
categories:
  - 算法
tags:
  - BFS
  - DFS
---

[题目链接](http://acm.neu.edu.cn/hustoj/problem.php?id=1682)

中文题。有两种方法：

第一种：枚举所有海洋的点，bfs搜索，标记陆地的点是第几天被淹没，然后DFS连通分量。

```cpp
#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, t;
int pic[2005][2005];
int vis[2005][2005];
int dir[4][2] = {0,1,0,-1,1,0,-1,0};
bool judge(int x, int y){
    if(x>=0 && x<n && y>=0 && y<m)
        return true;
    else return false;
}
void dfs(int x, int y, int cnt){
    if(!judge(x, y) || vis[x][y] || !pic[x][y]) return;
    vis[x][y] = 1;
    for(int i = 0; i < 4; i++){
        int x1 = x+dir[i][0];
        int y1 = y+dir[i][1];
        dfs(x1, y1, cnt);
    }
}
int main(){
    //freopen("a.txt", "r", stdin);
    while(scanf("%d %d %d", &n, &m, &t) != EOF){
        queue<int> q;
        for(int i = 0; i < n; i++){
            char ch[2005];
            scanf("%s", ch);
            for(int j = 0; j < m; j++){
                if(ch[j] == '#')
                    pic[i][j] = -1;
                else{
                    q.push(i*m+j);
                    pic[i][j] = 0;
                }
            }
        }
        for(int i = 0; i < n; i++){
            if(pic[i][0] == -1){
                pic[i][0] = 1;
                q.push(i*m);
            }
            if(pic[i][m-1] == -1){
                pic[i][m-1] = 1;
                q.push(i*m+m-1);
            }
        }
        for(int i = 0; i < m; i++){
            if(pic[0][i] == -1){
                pic[0][i] = 1;
                q.push(i);
            }
            if(pic[n-1][i] == -1){
                pic[n-1][i] = 1;
                q.push(m*(n-1)+i);
            }
        }
        while(!q.empty()){
            int f = q.front();
            q.pop();
            int x = f/m; int y = f%m;
            for(int i = 0; i < 4; i++){
                int x1 = x+dir[i][0];
                int y1 = y+dir[i][1];
                if(judge(x1, y1) && pic[x1][y1] == -1){
                    pic[x1][y1] = pic[x][y]+1;
                    q.push(x1*m+y1);
                }
            }
        }
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                if(pic[i][j] <= t)
                    pic[i][j] = 0;
        memset(vis, 0, sizeof(vis));
        int num = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                if(pic[i][j] && !vis[i][j])
                    dfs(i, j, ++num);
        cout << num <<endl;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(!pic[i][j])
                    cout << ".";
                else cout << "#";
            }
            cout << endl;
        }

    }
    return 0;
}
```

用queue写bfs的话1.7s过的，如果用数组搞bfs只有0.7s，差距非常感人。

第二种方法：在搜索连通分量之前，并不需要bfs，正反各遍历一遍图，就可以标记完成。

```cpp
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
int dis[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
char mp[2010][2010];
int TM[2010][2010];
bool vis[2010][2010];
int m,n,t;
struct mm{
    int x,y;
};
void bfs(int x,int y){
    queue <mm> q;
    mm st;
    st.x=x;
    st.y=y;
    vis[x][y]=1;
    q.push(st);
    while(!q.empty()){
        mm now=q.front();
        q.pop();
        mm next;
        for(int i=0;i<4;i++){
            next.x=now.x+dis[i][0];
            next.y=now.y+dis[i][1];
            if(!vis[next.x][next.y]&&TM[next.x][next.y]>t){
                vis[next.x][next.y]=1;
                q.push(next);
            }
        }
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d%d",&n,&m,&t)!=EOF){
        memset(vis,0,sizeof(vis));
        memset(TM,0,sizeof(TM));
        for(int i=0;i<n;i++){
            scanf("%s",mp[i]);
        }
        for(int j=0;j<m;j++){
            if(mp[0][j]=='.'){
                TM[0][j]=0;
            }
            else{
                TM[0][j]=1;
            }
            mp[0][j]='.';
            if(mp[n-1][j]=='.'){
                TM[n-1][j]=0;
            }
            else{
                TM[n-1][j]=1;
            }
            mp[n-1][j]='.';
        }
        for(int i=1;i<n-1;i++){
            if(mp[i][0]=='.'){
                TM[i][0]=0;
            }
            else{
                TM[i][0]=1;
            }
            mp[i][0]='.';
            if(mp[i][m-1]=='.'){
                TM[i][m-1]=0;
            }
            else{
                TM[i][m-1]=1;
            }
            mp[i][m-1]='.';
        }
        for(int i=1;i<n-1;i++){
            for(int j=1;j<m-1;j++){
                if(mp[i][j]=='.'){
                    TM[i][j]=0;
                }
                else{
                    int k=1000000;
                    k=min(k,TM[i-1][j]+1);
                    //k=min(k,TM[i+1][j]+1);
                    k=min(k,TM[i][j-1]+1);
                    //k=min(k,TM[i][j+1]+1);
                    TM[i][j]=k;
                    //printf("%d %d %dn",i,j,k);
                }
            }
        }
        /*for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                printf("%d",TM[i][j]);
            }
            printf("n");
        }*/
        for(int i=n-2;i>0;i--){
            for(int j=m-2;j>0;j--){
                if(mp[i][j]=='.'){
                    TM[i][j]=0;
                }
                else{
                    int k=1000000;
                    k=min(k,TM[i-1][j]+1);
                    k=min(k,TM[i+1][j]+1);
                    k=min(k,TM[i][j-1]+1);
                    k=min(k,TM[i][j+1]+1);
                    TM[i][j]=k;
                }
            }
        }
        int ans=0;
        for(int i=1;i<n-1;i++){
            for(int j=1;j<m-1;j++){
                if(!vis[i][j]&&mp[i][j]=='#'&&TM[i][j]>t){
                    ans++;
                    bfs(i,j);
                }
            }
        }
        /*for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                printf("%d",TM[i][j]);
            }
            printf("n");
        }*/
        printf("%dn",ans);
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(TM[i][j]<=t){
                    printf(".");
                }
                else{
                    printf("#");
                }
            }
            printf("n");
        }
    }
    return 0;
}
```

第二种方法只有0.5s