C++(g++ 7.5.0) 解法, 执行用时: 9ms, 内存消耗: 2884K, 提交时间: 2023-05-17 20:18:47

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=205;
char ap[N][N];
int bj[N][N];

int n,m,ret=0,flag;

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

void dfs(int x,int y)
{
	if(x==1||x==n||y==1||y==m)
	flag=1;
	bj[x][y]=1;
	for(int i=0;i<8;i++)
	{
		int sx=x+dx[i];
		int sy=y+dy[i];
		if(sx>=1&&sx<=n&&sy>=1&&sy<=m&&!bj[sx][sy]&&ap[sx][sy]=='#')
		{
			dfs(sx,sy);
			
		}
	}
}

signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>ap[i][j];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			flag=0;
			if(ap[i][j]!='#'||bj[i][j]) continue;
			dfs(i,j);
			if(!flag)
			ret++;	
		}
	}
	cout<<ret;
	return 0;
}
		

Python3 解法, 执行用时: 133ms, 内存消耗: 34240K, 提交时间: 2022-07-27 22:25:25

import sys   
sys.setrecursionlimit(100000)

n, m = map(int, input().split())
grid = []

for i in range(n):
    grid.append(list(input()))

near = []
for i in [-1, 0, 1]:
    for j in [-1, 0, 1]:
            near.append([i, j])
near.remove([0, 0])

def dfs(i, j):
    if i < 0 or j < 0 or i >= n or j >=m:
        return
    if grid[i][j] == '.':
        return
    grid[i][j] = '.'
    for k, l in near:
        dfs(i + k,j + l)

for i in range(n):
    dfs(i, 0)
    dfs(i, m - 1)
for j in range(1, m - 1):
    dfs(0, j)
    dfs(n - 1, j)

res = 0
for i in range(1, n - 1):
    for j in range(1, m - 1):
        if grid[i][j] == '#':
            res += 1
            dfs(i, j)
print(res)

Python2 解法, 执行用时: 124ms, 内存消耗: 31736K, 提交时间: 2022-04-07 16:01:25

import sys
sys.setrecursionlimit(1000000)

n, m = map(int, raw_input().split())
s = []
for i in xrange(n):
    s.append([j for j in raw_input()])

island = 0
def dfs(s, i, j):
    if i == 0 or i == n-1 or j == 0 or j == m-1:
        return False
    s[i][j] = '.'
    flag = True
    for k in xrange(i-1, i+2):
        for v in xrange(j-1, j+2):
            if k == i and v == j:
                continue
            if s[k][v] == "#":
                if not dfs(s, k, v):
                    flag = False
    return flag
for i in xrange(n):
    for j in xrange(m):
        if s[i][j] == '#':
            if dfs(s, i, j):
                island += 1
print island

C++(clang++ 11.0.1) 解法, 执行用时: 6ms, 内存消耗: 1280K, 提交时间: 2023-04-23 21:10:24

#include<iostream>
#include<algorithm> 
using namespace std;
const int N = 222;
char map[N][N];
int n,m,ans,sum;
int str[N][N];
int x1[]={0,0,-1,1,-1,-1,1,1};
int y1[]={-1,1,0,0,-1,1,-1,1};//上、下、左、右、左上、左下、右上、右下 
void dfs(int u,int v)
{
	int x,y;
	if(u==0||u==n-1||v==0||v==m-1)	sum=1;
	str[u][v]=1;
	for(int i=0;i<8;i++)
	{
		x=u+x1[i];
		y=v+y1[i];
		if(x>=0&&x<n&&y>=0&&y<m&&!str[x][y]&&map[x][y]=='#')
			dfs(x,y);
	}
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)
		cin>>map[i];
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			sum=0;
			if(map[i][j]!='#'||str[i][j])	continue;
				dfs(i,j);
			if(!sum)
				ans++;
		}
	}
	cout<<ans<<endl;
}