#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

namespace dts
{
    const int mx[12]={-2,-1,-1,-1, 0, 0,0,0, 1,1,1,2};
    const int my[12]={ 0,-1, 0, 1,-2,-1,1,2,-1,0,1,0};
    
    int n,m,fa[10000],vis[10000];
    char c[100][100];
    
    int checkc(int x,int y)
    {
        if (0<=x&&x<n&&0<=y&&y<m)
            return c[x][y]=='#';
        else
            return 0;
    }
    
    int number(int x,int y)
    {
        return x*m+y;
    }
    
    int findfa(int x)
    {
        if (fa[x]!=x)
            fa[x]=findfa(fa[x]);
        return fa[x];
    }
    
    void main()
    {
        while (~scanf("%d%d\n",&n,&m))
        {
            for (int i=0;i<n;scanf("\n"),i++)
                for (int j=0;j<m;j++)
                    scanf("%c",&c[i][j]);
            memset(fa,-1,sizeof(fa));
            for (int i=0;i<n;i++)
                for (int j=0;j<m;j++)
                    if (checkc(i,j))
                        fa[number(i,j)]=number(i,j);
            for (int i=0;i<n;i++)
                for (int j=0;j<m;j++)
                    if (checkc(i,j))
                        for (int k=0;k<12;k++)
                            if (checkc(i+mx[k],j+my[k]))
                                if (findfa(number(i,j))!=findfa(number(i+mx[k],j+my[k])))
                                    fa[findfa(number(i+mx[k],j+my[k]))]=findfa(number(i,j));
            int ans=0;
            memset(vis,0,sizeof(vis));
            for (int i=0;i<=number(n-1,m-1);i++)
                if (fa[i]!=-1)
                    if (vis[findfa(i)]==0)
                        ans++,vis[findfa(i)]=1;
            printf("%d\n",ans);
        }
    }
}

int main()
{
    dts::main();
}

讲解：

这道题一看，各位读者就知道是DFS求连通图，水~，在此贴出DFS的代码和BFS的代码以及编者自己歪歪出的并查集代码。

代码实现： DFS:

#include<iostream>
using namespace std;
const int nx[13]={0,1,-1,0,0,2,-2,0,0,1,-1,1,-1};
const int ny[13]={0,0,0,1,-1,0,0,2,-2,-1,1,1,-1};//方向数组
char a[1001][1001];
int n,m,ans;
void dfs(int x,int y)
{
int i;
if(x<1 || x>n || y<1 || y>m || a[x][y]!='#') return;
//越界或已走过就return
a[x][y]='-';//标记已走过
for(i=1;i<=12;i++) dfs(x+nx[i],y+ny[i]);
}
int main()
{
int i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) for(j=1;j<=m;j++) cin>>a[i][j];
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if (a[i][j]=='#')
{
ans++;
dfs(i,j);
}
}
}
cout<<ans;
}
BFS:

#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
char a[101][101];
int book[101][101],n,m;
struct note{int x,y;};
void bfs(int x,int y)
{

int tx,ty,k;
int next[12][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1},{-2,0},{0,-2},{0,2},{2,0}};
queue<note>q;
note z;
q.push((note){x,y});
book[x][y]=1;
while(!q.empty())
{

z=q.front();
for(k=0;k<12;k++)
{
tx=z.x+next[k][0];
ty=z.y+next[k][1];
if(tx<1||tx>n||ty<1||ty>m) continue;
if(a[tx][ty]=='#'&&book[tx][ty]==0)
{

book[tx][ty]=1;
q.push((note){tx,ty});
}
}
q.pop();
}
return;
}
int main()
{

int i,j,ans=0;
scanf("%d%d\n",&n,&m);
//编者实测，没有\n你会wa（wrong answer）
for(i=1;i<=n;i++) gets(a[i]+1);//没有你会tle（超时）
for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(a[i][j]=='#'&&!book[i][j]) bfs(i,j),ans++;
cout<<ans;

}
并查集：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int inf=110;
int a[inf][inf],n,m,ans,i,j,f[(inf+1)*(inf+1)];
int gets(int x)
{
if(f[x]==x) return x;
return f[x]=gets(f[x]);
}
void ff(int x,int y)
{
int t1=gets(x),t2=gets(y);
f[t1]=t2;
return;
}
int main()
{
char ch[inf];
scanf("%d%d",&n,&m);
for(i=1;i<=(n+1)*(inf+1)+(m+1);i++) f[i]=i;
for(i=1;i<=n;i++)
{
scanf("%s",&ch);
for(j=1;j<=m;j++)
{
if(ch[j-1]=='-') a[i][j]=0;
else a[i][j]=1;
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(a[i][j]==0) continue;
if(i-1>=1 && a[i-1][j]!=0) ff((i-1)*inf+j,i*inf+j);
if(i-2>=1 && a[i-2][j]!=0) ff((i-2)*inf+j,i*inf+j);
if(i+1<=n && a[i+1][j]!=0) ff((i+1)*inf+j,i*inf+j);
if(i+2<=m && a[i+2][j]!=0) ff((i+2)*inf+j,i*inf+j);
if(j-1>=1 && a[i][j-1]!=0) ff(i*inf+(j-1),i*inf+j);
if(j-2>=1 && a[i][j-2]!=0) ff(i*inf+(j-2),i*inf+j);
if(j+1<=m && a[i][j+1]!=0) ff(i*inf+(j+1),i*inf+j);
if(j+2<=m && a[i][j+2]!=0) ff(i*inf+(j+2),i*inf+j);
if(i-1>=1 && j-1>=1 && a[i-1][j-1]!=0) ff((i-1)*inf+(j-1),i*inf+j);
if(i-1>=1 && j+1<=m && a[i-1][j+1]!=0) ff((i-1)*inf+(j+1),i*inf+j);
if(i+1<=n && j-1>=1 && a[i+1][j-1]!=0) ff((i+1)*inf+(j-1),i*inf+j);
if(i+1<=n && j+1<=m && a[i+1][j+1]!=0) ff((i+1)*inf+(j+1),i*inf+j);
}
}
for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(f[i*inf+j]==i*inf+j && a[i][j]!=0) ans++;
printf("%d",ans);
return 0;
}

bfs，找联通块，挺基础的一道题

#include<iostream>
#include<queue>
using namespace std;

int n,m,ans;
char s[105][105];
bool vis[105][105];
int dx[] = {-2,-1,0,1,2,1,0,-1,-1,0,1,0};
int dy[] = {0,1,2,1,0,-1,-2,-1,0,1,0,-1};
struct Node{
    int x,y;
    Node(int a,int b)
    {
        x = a;
        y = b;
    }
};

queue<Node> q;
void bfs(int x,int y)
{
    q.push(Node(x,y));
    vis[x][y] = 1;
    while(!q.empty())
    {
        Node now = q.front();
        q.pop();
        for(int i = 0;i < 12;i++)
        {
            int xx = dx[i]+now.x;
            int yy = dy[i]+now.y;
            if(!vis[xx][yy]&&xx >= 1&&xx <= n&&yy >= 1&&yy <= m&&s[xx][yy] != '-')
            {
                vis[xx][yy] = 1;
                q.push(Node(xx,yy));
            }
        }
    }
}
int main(void)
{
    cin>>n>>m;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            cin>>s[i][j];
        }
    }
    
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            if(s[i][j] == '#'&&!vis[i][j])
            {
                bfs(i,j);
                ans++;
            }
        }
    }
    
    cout<<ans<<endl;
    return 0;
}

使用DFS进行深度优先搜索，由*题目定义*确定**访问路径**：

#include <iostream>
#include <stdio.h>
#include <vector>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn = 1010;
char G[maxn][maxn];
bool vis[maxn][maxn];
int n, m; //for n(y) rows and m(x) collumns
int X[12] = { 0, 0, 1, 1, 2, 1, 0, 0, -1, -1, -2, -1 };
int Y[12] = { 2, 1, 1, 0, 0, -1, -1, -2, -1, 0, 0, 1 };

bool judge(int y, int x)
{//whether across the boarder
    if (x < 0 || y >= n || x >= m || y < 0) {
        return false;
    }
    if (vis[y][x] == true) {
        return false;
    }
    return true;
}

void DFS(int y, int x)
{
    if (!judge(y, x)) {//already visited
        return;
    }
    vis[y][x] = true;
    for (int i = 0; i < 12; i++) {
        if (G[y][x] == '#') {
            DFS(y + Y[i], x + X[i]);
        }
        else {
            break;
        }
    }
}

int DFS_traverse()
{
    int block = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (G[i][j] == '#' && judge(i, j)) {//is '#' not '-'
                block++;
            }
            DFS(i, j);
        }
    }
    return block;
}

int main()
{
    scanf("%d%d", &n, &m);
    fill(vis[0], vis[0] + maxn * maxn, false);
    fill(G[0], G[0] + maxn * maxn, '-');
    for (int i = 0; i < n; i++) {
        scanf("%s", &G[i]); //using scanf("%c", G[i][j]); will cause fatal input error
    }
    for (int i = 0; i < n; i++) {//mark: '-' is unreachable boarder
        for (int j = 0; j < m; j++) {
            if (G[i][j] == '-') {
                vis[i][j] = true;
            }
        }
    }
    int block = 0;
    block = DFS_traverse();
    cout << block;
    return 0; 
}

bfs 用了STL的queue和set

#include<bits/stdc++.h>
using namespace std;
queue<pair<int,int>> q;
set<pair<int,int>> s;
set<pair<int,int>>::iterator it;
char c[110][110];
int v[110][110];
int d[2][12] = {{1,-1,0,0,2,-2,0,0,1,-1,1,-1},{0,0,1,-1,0,0,2,-2,1,1,-1,-1}};
int main(){
    int n,m,k=0;
    pair<int,int> cur;
    scanf("%d%d",&n,&m);
    getchar();
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf("%c",&c[i][j]);
            if(c[i][j]=='#') s.insert(make_pair(i,j));
        }
        getchar();
    }
    while(!s.empty()){
        it = s.begin();
        cur = *it; s.erase(cur);
        q.push(cur);
        while(!q.empty()){
            cur = q.front(); q.pop();
            v[cur.first][cur.second] = 1;
            for(int j=0;j<12;j++){
                int x = cur.first+d[0][j], y = cur.second+d[1][j];
                if(x<0||y<0||x>=n||y>=m||v[x][y]==1 || c[x][y]!='#') continue;
                q.push(make_pair(x,y));
                s.erase(make_pair(x,y));
                v[x][y] = 1;
            }
        }
        k++;
    }
    printf("%d",k);
}

//一个效率极其低下的bfs
const
    dx:array[1..12] of -2..2 = (-2,-1,-1,-1,0,0,0,0,1,1,1,2);
    dy:array[1..12] of -2..2 = (0,-1,0,1,-2,-1,1,2,-1,0,1,0);
var
    a:array[-11..111,-11..111] of char;
    i,j,n,m,ans:longint;
    
procedure bfs(x,y:longint);
var
    qx,qy:array[1..100001] of longint;
    i,l,r:longint;
    
function exist(x,y,l,r:longint):boolean;
var i:longint;
begin
    for i:=l to r-1 do if (qx[i]=x) and (qy[i]=y) then exit(true);
    exit(false);
end;
    
begin
    l:=1; r:=2; qx[l]:=x; qy[l]:=y;
    while l<r do begin
        a[qx[l],qy[l]]:='-';
        for i:=1 to 12 do
            if (a[qx[l]+dx[i],qy[l]+dy[i]]='#') and not exist(qx[l]+dx[i],qy[l]+dy[i],l,r) then begin
                qx[r]:=qx[l]+dx[i]; qy[r]:=qy[l]+dy[i]; inc(r);
            end;
        inc(l);
    end;
    inc(ans);
end;

begin
    readln(n,m);
    fillchar(a,sizeof(a),'-');
    for i:=1 to n do begin
        for j:=1 to m do
            read(a[i,j]);
        readln;
    end;
    for i:=1 to n do
        for j:=1 to m do
            if a[i,j]='#' then bfs(i,j);
    writeln(ans);
end.

水题.⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄

#include<iostream>
using namespace std;
char tu[150][150];
int ans=0;
int n,m;
void dfs(int x,int y)
{
    tu[x][y]='.';
    if(tu[x-2][y]=='#')
    dfs(x-2,y);
    if(tu[x-1][y]=='#')
    dfs(x-1,y);
    if(tu[x-1][y+1]=='#')
    dfs(x-1,y+1);
    if(tu[x][y+1]=='#')
    dfs(x,y+1);
    if(tu[x][y+2]=='#')
    dfs(x,y+2);
    if(tu[x+1][y+1]=='#')
    dfs(x+1,y+1);
    if(tu[x+2][y]=='#')
    dfs(x+2,y);
    if(tu[x+1][y]=='#')
    dfs(x+1,y);
    if(tu[x+1][y-1]=='#')
    dfs(x+1,y-1);
    if(tu[x][y-1]=='#')
    dfs(x,y-1);
    if(tu[x][y-2]=='#')
    dfs(x,y-2);
    if(tu[x-1][y-1]=='#')
    dfs(x-1,y-1);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            cin>>tu[i][j];
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            if(tu[i][j]=='#')
            {
            ans++;
            dfs(i,j);
            }
        }
    }
    cout<<ans;
    return 0;
}

这才是完美题解，@YLFX以后别抄我的题解了啊！！！
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
char map[100][100];
bool visited[100][100];
int change[2][12]= {{0,-1,0,1,-2,-1,1,2,-1,0,1,0},{-2,-1,-1,-1,0,0,0,0,1,1,1,2}};
int cc=0;
int m,n;
struct point {
int r,c;
};
queue<point> q;
void BFS(int r,int c) {
int i,newr,newc;
bool yes;
point p;
point cookie;
p.r=r;
p.c=c;
q.push(p);
visited[r][c]=1;
while(!q.empty()) {
p=q.front();
q.pop();
yes=0;
for(i=0; i<12; i++) {
newr=p.r+change[0][i];
newc=p.c+change[1][i];
if(newc<m&&newc>=0&&newr<n&&newr>=0&&visited[newr][newc]==0&&map[newr][newc]=='#') {
cookie.r=newr;
cookie.c=newc;
q.push(cookie);
visited[newr][newc]=1;
}
}
}
cc++;
}
int main() {
memset(map,'-',sizeof(map));
memset(visited,0,sizeof(visited));
int i,j;
cin>>n>>m;
for(i=0; i<n; i++) {
for(j=0; j<m; j++)
cin>>map[i][j];
}
for(i=0; i<n; i++) {
for(j=0; j<m; j++)
if(visited[i][j]==0&&map[i][j]=='#')
BFS(i,j);
}
cout<<cc;
return 0;
}

***上了贼船就应该跟贼走，用了变量就要用到底
DFS。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
char map[100][100];
bool visited[100][100];
int change[2][12]= {{0,-1,0,1,-2,-1,1,2,-1,0,1,0},{-2,-1,-1,-1,0,0,0,0,1,1,1,2}};
int cc=0;
int m,n;
struct point {
    int r,c;
};
queue<point> q;
void BFS(int r,int c) {
    int i,newr,newc;
    bool yes;
    point p;
    point cookie;
    p.r=r;
    p.c=c;
    q.push(p);
    visited[r][c]=1;
    while(!q.empty()) {
        p=q.front();
        q.pop();
        yes=0;
        for(i=0; i<12; i++) {
            newr=p.r+change[0][i];
            newc=p.c+change[1][i];
            if(newc<m&&newc>=0&&newr<n&&newr>=0&&visited[newr][newc]==0&&map[newr][newc]=='#') {
                cookie.r=newr;
                cookie.c=newc;
                q.push(cookie);
                visited[newr][newc]=1;
            }
        }
    }
    cc++;
}
int main() {
    memset(map,'-',sizeof(map));
    memset(visited,0,sizeof(visited));
    int i,j;
    cin>>n>>m;
    for(i=0; i<n; i++) {
        for(j=0; j<m; j++)
            cin>>map[i][j];
    }
    for(i=0; i<n; i++) {
        for(j=0; j<m; j++)
            if(visited[i][j]==0&&map[i][j]=='#')
                BFS(i,j);
    }
    cout<<cc;
    return 0;
}

---

bfs
~~~
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int N = 100 + 2;
char c;
int m,n,t = 0,A[N][N],used[N][N];
void read()
{
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
A[i][j] = used[i][j] = 0;
scanf("%d%d\n",&n,&m);
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
scanf("%c",&c);
if(c == '#') A[i][j] = 1;
}
scanf("\n");
}
}
void search(int x,int y)
{
if(!A[x][y] || used[x][y]) return;
used[x][y] = 1;
if(x > 1)search(x - 2,y);
search(x - 1,y - 1);
search(x - 1,y);
search(x - 1,y + 1);
if(y > 1)search(x,y - 2);
search(x,y - 1);
search(x,y + 1);
if(y < m)search(x,y + 2);
search(x + 1,y - 1);
search(x + 1,y);
search(x + 1,y + 1);
if(x < n)search(x + 2,y);
}
void bfs()
{
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
{
if(A[i][j] && !used[i][j])
{
t++;
search(i,j);
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
read();
/*for(int i = 1;i <= n;i++)
{
for(int j =1;j <= m;j++)
printf("%d",A[i][j]);
printf("\n");
}*/
bfs();
printf("%d\n",t);
return 0;
}
~~~

广度优先搜索
```c++
#include <iostream>
#include <list>
#include <queue>

using namespace std;

struct Point {
Point() : x(0), y(0) {}
Point(int _x, int _y) : x(_x), y(_y) {}

int x;
int y;
}; // struct Point

typedef list<Point> ListType;
typedef queue<Point, ListType> Queue;

#define DEBUG false

#define NMAX 100
#define UNLIGHT '-'
#define LIGHTED '#'

static int marked[NMAX][NMAX];
static bool map[NMAX][NMAX];
static int n, m;

int Search();
void _PrintMap();
void _PrintMarked();

inline bool Check(const int x, const int y) {
return marked[x][y] == 0 and map[x][y];
}

inline bool Check(const Point &p) { return Check(p.x, p.y); }

inline bool CheckPlacable(const int x, const int y) {
return 0 <= x and x < n and 0 <= y and y < m and Check(x, y);
}

inline bool CheckPlacable(const Point &p) { return CheckPlacable(p.x, p.y); };

int main() {
ios::sync_with_stdio(false);

cin >> n >> m;
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) {
char c;
cin >> c;

if (c == UNLIGHT) { map[x][y] = false; } else {
map[x][y] = true;
}

marked[x][y] = 0;
} // for
} // for

cout << Search();

if (DEBUG) {
_PrintMap();
cout << endl;
_PrintMarked();
}

return 0;
} // function main

int Search() {
#define STATUS_SIZE 12

const int dx[STATUS_SIZE] = { -2, -1, -1, -1, 0, 0, 0, 0, 1, 1, 1, 2 };
const int dy[STATUS_SIZE] = { 0, -1, 0, 1, -2, -1, 1, 2, -1, 0, 1, 0 };

Queue q;
int id = 1;

for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) {
if (Check(x, y)) {
q.push(Point(x, y));

while (!q.empty()) {
Point p = q.front();
q.pop();

if (Check(p)) {
marked[p.x][p.y] = id;

for (int i = 0; i < STATUS_SIZE; i++) {
if (CheckPlacable(p.x + dx[i], p.y + dy[i])) {
q.push(Point(p.x + dx[i], p.y + dy[i]));
}
} // for
}

} // while

id++;
}
} // for
} // for

return id - 1;

#undef STATUS_SIZE
}

void _PrintMap() {
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) { cout << map[x][y]; } // for

cout << endl;
} // for
}

void _PrintMarked() {
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) { cout << marked[x][y] << " "; } // for

cout << endl;
} // for
}

###简单的广搜

记录信息
评测状态 Accepted
题目 P1051 送给圣诞夜的极光
递交时间 2015-09-05 22:38:06
代码语言 C++
评测机 VijosEx
消耗时间 54 ms
消耗内存 1316 KiB
评测时间 2015-09-05 22:38:07
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 536 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 612 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 608 KiB, score = 10
测试数据 #3: Accepted, time = 3 ms, mem = 632 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 636 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 536 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 544 KiB, score = 10
测试数据 #8: Accepted, time = 36 ms, mem = 636 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 1316 KiB, score = 10
Accepted, time = 54 ms, mem = 1316 KiB, score = 100
代码
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;
char map[110][110];
bool been[110][110];
int n,m,ans;
void search(int x,int y)
{
for(int i=-2;i<=2;i++)
{
for(int j=-2;j<=2;j++)
{
if(abs(i)+abs(j)>2) continue;
if(x+i>=0&&x+i<n)
if(y+j>=0&&y+j<m)
if(map[x+i][y+j]=='#'&&!been[i+x][j+y])
{
been[i+x][y+j]=1;
search(i+x,y+j);
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%s",map[i]);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(map[i][j]=='#'&&!been[i][j])
{
been[i][j]=1;
ans++;
search(i,j);
}
}
printf("%d",ans);
}

FLOODFILL轻松过
代码如下：
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

char light[105][105];
bool visited[105][105];
int M,N;
int Fx[]={1,-1,2,-2,0,0,0,0,1,1,-1,-1};
int Fy[]={0,0,0,0,1,-1,2,-2,1,-1,1,-1};

void init(){
cin>>N>>M;
int i,j;
for(i=0;i<N;i++)
for(j=0;j<M;j++)
cin>>light[i][j];
return;
}

void floodfill(int x,int y){
visited[x][y]=true;
int i,dx,dy;
for(i=0;i<12;i++){
dx=x+Fx[i];
dy=y+Fy[i];
if(dx>=0&&dx<N&&dy>=0&&dy<M&&!visited[dx][dy]&&light[dx][dy]=='#')
floodfill(dx,dy);
}
return;
}

void memset(){
int i,j;
for(i=0;i<100;i++)
for(j=0;j<100;j++)
visited[i][j]=false;
return;
}

int main(){
init();
int i,j,ans=0;
memset();
for(i=0;i<N;i++)
for(j=0;j<M;j++)
if(light[i][j]=='#'&&!visited[i][j]){
floodfill(i,j);
ans++;
}
cout<<ans;
return 0;
}

暴力深搜
#include<cmath>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#define LL long long
#define for1(v,a,b) for (int v=a;v<=b;v++)
#define for2(v,a,b) for (int v=a;v>=b;v--)
using namespace std;
int map[101][101];
int n,m,ans;
void Init(){
char ch;
scanf("%d%d",&n,&m);
scanf("%c",&ch);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%c",&ch);
if (ch=='#') map[i][j]=0;
else map[i][j]=-1;
}
scanf("%c",&ch);
}
}
bool Permit(int x,int y){
if ((x<=0)||(x>n)||(y<=0)||(y>m)) return false;
if (map[x][y]!=0) return false;
return true;
}
void Dfs(int x,int y){
map[x][y]=ans;
if (Permit(x+1,y)) Dfs(x+1,y);
if (Permit(x+2,y)) Dfs(x+2,y);
if (Permit(x-1,y)) Dfs(x-1,y);
if (Permit(x-2,y)) Dfs(x-2,y);
if (Permit(x,y+1)) Dfs(x,y+1);
if (Permit(x,y+2)) Dfs(x,y+2);
if (Permit(x,y-1)) Dfs(x,y-1);
if (Permit(x,y-2)) Dfs(x,y-2);
if (Permit(x+1,y+1)) Dfs(x+1,y+1);
if (Permit(x-1,y+1)) Dfs(x-1,y+1);
if (Permit(x+1,y-1)) Dfs(x+1,y-1);
if (Permit(x-1,y-1)) Dfs(x-1,y-1);
}
int main(){
//freopen("p1.in","r",stdin);
Init();
ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if (map[i][j]==0){
ans++;
Dfs(i,j);
}
printf("%d",ans);
return 0;
}

广搜为什么错了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

#include<cstdlib>

#include<queue>

#include<cmath>
using namespace std;
int n,m,ans,b[12][2]={{1,0},{2,0},{-1,0},{-2,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1},{0,2},{0,-2}};
char a[240][240];
bool v[240][240];
struct node
{
int x,y;
}first;
void bfs()
{
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(a[i][j]=='#'&&v[i][j]==0)
{
first.x=i;
first.y=j;
ans++;

queue<node> q;
q.push(first);
v[first.x][first.y]=1;
while(!q.empty())
{
node now,next;
now=q.front();
q.pop();
for(int i=0;i<12;i++)
{
next.x=now.x+b[i][0];
next.y=now.y+b[i][1];
if(0<=next.x&&next.x<m&&0<=next.y&&next.y<n&&a[next.x][next.y]=='#'&&v[next.x][next.y]==0)
{
v[next.x][next.y]=1;
q.push(next);
}
}
}
}
}
}
return ;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
memset(v,0,sizeof(v));

bfs();
cout<<ans;
return 0;
}

以每个没有访问的点为源点开始访问，总共的访问次数就是答案。

Pascal Code

const
    dx:array[1..12] of longint=(0,1,1,1,0,-1,-1,-1,0,2,0,-2);
    dy:array[1..12] of longint=(1,0,1,-1,-1,-1,1,0,2,0,-2,0);
var
    b:longint;
    v:array[1..100,1..100] of boolean;    //v数组存储是否访问过
    m,n,i,j:longint;
    c:char;
procedure visit(x,y:longint);
var i:longint;
begin
    if v[x,y] then exit;
    v[x,y]:=true;
    for i:=1 to 12 do
    begin
        if x+dx[i]<1 then continue;    //判断是否超范围
        if x+dx[i]>n then continue;
        if y+dy[i]<1 then continue;
        if y+dy[i]>m then continue;
        visit(x+dx[i],y+dy[i]);
    end;
end;
begin
    readln(n,m);
    fillchar(v,sizeof(v),0);
    for i:=1 to n do
    begin
        for j:=1 to m do
        begin
            read(c);
            if c='-' then v[i,j]:=true;    //如果不发光则视为已访问过
        end;
        readln;
    end;
    b:=0;
    for i:=1 to n do
        for j:=1 to m do
            if not v[i,j]
            then begin
                         visit(i,j);
                         inc(b);
                     end;
    writeln(b);
end.

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<math.h>
using namespace std;
bool a[105][105];
int xsize, ysize;
int ans = 0;
int ab(int n){
if (n < 0)return -n;
else return n;
}
void visit(int x, int y){
if (x < 0 || y < 0)return;
if (x >= xsize || y>ysize)return;
if (a[x][y] == false)return;
a[x][y] = false;
visit(x - 2, y);
int i, j;
for (i = -2; i <= 2; i++){
for (j = -(ab(2 - ab(i))); j <= ab(2 - ab(i)); j++){
visit(x + i, y + j);
}
}
}
void go(){
int i, j;
for (i = 0; i < xsize; i++){
for (j = 0; j < ysize; j++){
if (a[i][j]){
ans++;
visit(i, j);
}
}
}
}
int main(){
freopen("in.txt", "r", stdin);
cin >> xsize >> ysize;
int i, j;
char c;
memset(a, 0, sizeof(a));
for (i = 0; i < xsize;i++)
for (j = 0; j < ysize; j++){
cin >> c;
if (c == '#')a[i][j] = true;
}
go();
cout << ans << endl;
return 0;
}

当作Bfs的小练习吧..
#include <cstdio>
#include <cstring>
using namespace std;
int s[10];
int dx[]={0,0,0,1,-1,0,0,2,-2,1,1,-1,-1};
int dy[]={0,1,-1,0,0,2,-2,0,0,-1,1,1,-1};
const int maxn=1000000+10;
struct node {
int x,y;
}team[maxn];
bool hash[110][110];
int bj[110][110];
char map[110][110];
int ans=0,n,m;
void Bfs(int s,int t)
{
memset(hash,0,sizeof(hash));
ans++;
int head=0,tail=1;
team[tail].x=s;
team[tail].y=t;
hash[s][t]=1;
bj[s][t]=ans;
while(head!=tail)
{
head++;
for(int i=1;i<=12;i++)
{
int px=team[head].x+dx[i];
int py=team[head].y+dy[i];
if(px<=n && px>=1 && py>=1 && py<=m && !hash[px][py] &&!bj[px][py] && map[px][py]!='-')
{
tail++;
team[tail].x=px;
team[tail].y=py;
bj[px][py]=bj[team[head].x][team[head].y];
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",&map[i][1]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(map[i][j]=='#' && !bj[i][j])
Bfs(i,j);
printf("%d",ans);
return 0;
}

var
m,n,i,j,num,a,b:integer;
tu:array[1..100,1..100]of integer;
ax:array[1..12]of integer=(-2,-1,-1,-1,0,0,0,0,1,1,1,2);
ay:array[1..12]of integer=(0,-1,0,1,-2,-1,1,2,-1,0,1,0);
procedure readin;
var
i,j:integer;
k:char;
begin
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
begin
read(k);
if k='-' then tu[i,j]:=0
else tu[i,j]:=1;
end;
readln;
end;
end;

procedure work(x,y:integer);
var
i,j:integer;
begin
tu[x,y]:=0;
for i:=1 to 12 do
if (x+ax[i]<=n)and(x+ax[i]>=1)and(y+ay[i]<=m)and(y+ay[i]>=1) then
if tu[x+ax[i],y+ay[i]]=1 then
work(x+ax[i],y+ay[i]);
end;
begin
readin;
num:=0;
for i:=1 to n do
for j:=1 to m do
if tu[i,j]=1 then
begin
work(i,j);
num:=num+1;
end;
write(num);
end.

program p1051;
var
a:array[-1..102,-1..102]of char;
n,m,i,j,ans:longint;
procedure dfs(c,d:longint);
begin
if a[c,d]='#' then begin
a[c,d]:='-';
dfs(c+1,d);dfs(c+2,d);
dfs(c-1,d);dfs(c-2,d);
dfs(c,d+1);dfs(c,d+2);
dfs(c,d-1);dfs(c,d-2);
dfs(c+1,d+1);dfs(c-1,d+1);
dfs(c-1,d-1);dfs(c+1,d-1);end;
end;
begin
readln(n,m);
for i:=1 to n do begin for j:=1 to m do read(a[i,j]);readln;end;
for i:=1 to n do for j:=1 to m do
if a[i,j]='#' then begin dfs(i,j);inc(ans);end;
writeln(ans);
end.