今天詳細(xì)看了一下BFS
算法和之前學(xué)習(xí)的……emmmmmm可能開始不夠吧
先看一下藍(lán)橋杯一道全球變暖的題……恨不得練10000道讓我信手捏來一個(gè)dfs
第一遍一直提醒自己遞歸庙楚，然而……
思路就是最開始統(tǒng)計(jì)一下多少個(gè)島嶼
然后淹沒之后統(tǒng)計(jì)島嶼相減
然而第一遍每次都是從頭到尾遍歷层亿，相當(dāng)于樹的層序遍歷吧，復(fù)雜度極高，運(yùn)行時(shí)間也很長

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
int n;
char MAP[1005][1005];

struct plain{
    bool tag;
    bool drown;
    int k;
};
plain MAP2[1005][1005];

int dir[4][2]={-1,0,1,0,0,-1,0,1};
int K=1;
void visit(char MAP[1005][1005],int x,int y){

    bool flag=false;
    if(MAP[x][y]=='#'){ 
    for(int i=0;i<4;i++){
            int X=x+dir[i][0];
            int Y=y+dir[i][1];//重新定義避免影響其他方向 
            
            if(MAP[X][Y]=='.') 
            {
            MAP2[x][y].drown=true;  
            }
            if(MAP[X][Y]=='#')
            {
                if(MAP2[X][Y].tag==false)flag=true;
                MAP2[X][Y].k=K;
            }
            MAP2[x][y].tag=true;
        }
        if(flag==false)K++;
        cout<<K<<"#"<<endl;
    }
} 



int main()
{
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%s",MAP[i]);
    for(int j=0;j<n;j++){
        if(MAP[i][j]=='#')
        {
            plain p;
            p.drown=p.tag=false;
            p.k=0;
            MAP2[i][j]=p;
        }
    }
}
for(int i=1;i<n-1;i++){
    for(int j=1;j<n-1;j++){
        visit(MAP,i,j);
    }
}
   for(int i=0;i<n;i++){
     for(int j=0;j<n;j++){
    printf("%d ",MAP2[i][j].k);
  }
  cout<<endl;
}
int drown_il=0;

for(int K2=1;K2<K;){
for(int i=1;i<n;i++){
     for(int j=1;j<n;j++){
        if(MAP[i][j]=='#')
        {
        if(MAP2[i][j].k==K2&&MAP2[i][j].drown==false)drown_il+=1;
        if(MAP2[i][j].k!=K2)K2++;
        }
     }
     
   }
}
cout<<drown_il<<endl;
  return 0;
}

第二遍倒是用了遞歸dfs……然鵝冕茅，按照我之前的思路統(tǒng)計(jì)島嶼個(gè)數(shù)落午，就是如果一片土地周圍除了海被訪問過的島，他就是這片島的最后一個(gè)……就是這個(gè)zz算法完全會(huì)把一個(gè)島切成2個(gè)啊
受不了自己的智商……就這樣吧 打印準(zhǔn)考證去了……

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
int n;
char MAP[1005][1005];
char MAP2[1005][1005];
int dir[4][2]={-1,0,1,0,0,-1,0,1};
int K=1;

void drown(int x,int y){
    for(int i=0;i<4;i++){
            cout<<"###"<<x<<y<<endl;
            int X=x+dir[i][0];
            int Y=y+dir[i][1];//重新定義避免影響其他方向 
            if(MAP2[X][Y]=='.'){
                cout<<"###"<<x<<y<<endl;
            MAP2[x][y]='^';
            }
        }
}
bool is_ilse(int x,int y){
    bool flag=true;
    for(int i=0;i<4;i++){
            int X=x+dir[i][0];
            int Y=y+dir[i][1];//重新定義避免影響其他方向 
            if(MAP2[X][Y]=='#')flag=false;
        }
        cout<<x<<" "<<y<<" falg"<<flag<<endl;
        if(flag==true)return 1;
        if(flag==false)return 0;
}

void dfs(int x,int y,int &count_p){
    if(is_ilse(x,y))
    {
        MAP2[x][y]='@';
    count_p++;
    return;
    }
    MAP2[x][y]=-1;
        for(int i=0;i<4;i++){
            int X=x+dir[i][0];
            int Y=y+dir[i][1];
            if(MAP2[X][Y] == '#'){
                dfs(X,Y,count_p);
            }
    }
} 

int main()
{
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%s",MAP[i]);
    }
for(int i=0;i<n;i++){
     for(int j=0;j<n;j++){
     MAP2[i][j]=MAP[i][j];
    }
}
int begin=0;
int end=0;

for(int i=1;i<n;i++){
     for(int j=1;j<n;j++){
        if(MAP2[i][j]=='#')
        dfs(i,j,begin);
    }
}
for(int i=0;i<n;i++){
     for(int j=0;j<n;j++){
        if(MAP[i][j]=='#')
        drown(i,j);
    }
}
   for(int i=0;i<n;i++){
     for(int j=0;j<n;j++){
    printf("%d ",MAP2[i][j]);
  }
  cout<<endl;
}
cout<<endl;
for(int i=0;i<n;i++){
     for(int j=0;j<n;j++){
        if(MAP[i][j]=='@')
        dfs(i,j,end);
    }
}
   for(int i=0;i<n;i++){
     for(int j=0;j<n;j++){
    printf("%d ",MAP2[i][j]);
  }
  cout<<endl;
}
cout<<begin<<" "<<end<<endl;

  return 0;
}