FloodFill水过

#include <iostream>

using namespace std;

const int N = 100;

char a[N + 1][N + 1];
char s[N + 1];
int n, m;

void FloodFill(int x, int y)
{
if (x <= 0 || y <= 0 || x > n || y > m) return;
if (a[x][y] == '-') return;
a[x][y] = '-';
FloodFill(x - 2, y);
FloodFill(x - 1, y);
FloodFill(x + 1, y);
FloodFill(x + 2, y);
FloodFill(x, y - 2);
FloodFill(x, y - 1);
FloodFill(x, y + 1);
FloodFill(x, y + 2);
FloodFill(x - 1, y - 1);
FloodFill(x - 1, y + 1);
FloodFill(x + 1, y - 1);
FloodFill(x + 1, y + 1);
}

int main()
{
int i, j;
cin >> n >> m;
for (i = 1; i <= n; ++i) {
cin >> s;
for (j = 1; j <= m; ++j) {
a[i][j] = s[j - 1];
}
}

int sum = 0;
for (i = 1; i <= n; ++i) {
for (j = 1; j <= m; ++j) {
if (a[i][j] == '#') {
++sum;
FloodFill(i, j);
}
}
}

cout << sum;

return 0;
}

#include <iostream>
using namespace std;
int c[13]={1,1,0,1,-1,0,2,0,-2,0,-1,-1,1};
char a[102][102];
void f(int x,int y)
{for(int i=0;i<=11;i++)
if(a[x+c[i]][y+c[i+1]]=='#')
{a[x+c[i]][y+c[i+1]]='-';f(x+c[i],y+c[i+1]);}}
int main()
{ int n,m,s=0;cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
{if(a[i][j]=='#'){a[i][j]='-';f(i,j);s++;}}
cout<<s<<endl;
return 0;}
##15行刷——你敢更短吗

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

using namespace std;
char c[110][110];
int belong[110][110];
int ans=0;

int dx[12] = {-1, -1,-1, 0, 0, 1, 1, 1, -2, 0, 0, 2},
dy[12] = {-1, 0, 1, -1, 1, -1, 0,1, 0, -2, 2, 0};
int n,m;
void dfs(int x, int y)
{
belong[x][y]=ans;
for (int i=0; i<12; i++)
if(dx[i]+x < n && dx[i]+x >= 0 && dy[i]+y < m && dy[i]+y >= 0 &&
!belong[dx[i]+x][dy[i]+y] && c[dx[i]+x][dy[i]+y]=='#')
dfs(dx[i]+x, dy[i]+y);
}

int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++) scanf("%s", c[i]);
memset(belong, 0, sizeof(belong));
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
if (c[i][j]=='#' && !belong[i][j]) {ans++; dfs(i,j);}
printf("%d", ans);
}

用并查集，对于距离小于等于2的两个点，union他们，之后统计有多少个点的father是自己就行了，时间效率O（M^2），M为点的数量

一开始用boolean类型数组来存地图，结果wrong了
后来用char类型数组存，AC了？
可以这样的吗！！

暴力搜索12个位置 可行则变成-

第一遍居然只过了1和10两组数据，仔细检查一下发现我把哈密顿距离小于2当成八连块来做了，漏掉了上下左右的4个解。
一道教科书级别的DFS题目，挺简单的。一上来要注意上下左右各空两行，以保证下标不溢出。同时写入数据的时候要注意下标。
C++ Code:
#include<iostream>
#include<string>
using namespace std;

bool pattern[104][104];
bool searched[104][104];

void dfs(int i,int j);

int main(){
for (int i=0;i<102;i++){
for(int j=0;j<102;j++){
pattern[i][j]=false;
searched[i][j]=false;
}
}

int num=0;
int n,m;
cin>>n>>m;
for (int i=2;i<=n+1;i++){
string a;
cin>>a;
const char *b=a.c_str();
for(int j=2;j<=m+1;j++){
if (b[j-2]=='#'){
pattern[i][j]=true;
}
}
}

for (int i=2;i<=n+1;i++){
for(int j=2;j<=m+1;j++){
if(searched[i][j]==false && pattern[i][j]==true){
num++;
dfs(i,j);
}
}
}
cout<<num;
return 0;

}

void dfs(int i,int j){
if(searched[i][j]==true || pattern[i][j]==false){
return;
}

searched[i][j]=true;
for (int x=-1;x<=1;x++){
for(int y=-1;y<=1;y++){
dfs(i+x,j+y);
}
dfs(i-2,j);dfs(i+2,j);dfs(i,j+2);dfs(i,j-2);
}
}

include <iostream>
using namespace std;

char a[100][100];
int f[100][100];
int n,m,i,j,s;
void try1(int k,int l)
{
f[k][l]=0;
if(k+1<n && a[k+1][l]=='#' && f[k+1][l]==1) try1(k+1,l);
if(k-1>=0&& a[k-1][l]=='#' && f[k-1][l]==1) try1(k-1,l);
if(l+1<m && a[k][l+1]=='#' && f[k][l+1]==1) try1(k,l+1);
if(l-1>=0&& a[k][l-1]=='#' && f[k][l-1]==1) try1(k,l-1);

if(k+2<n && a[k+2][l]=='#' && f[k+2][l]==1) try1(k+2,l);
if(k-2>=0&& a[k-2][l]=='#' && f[k-2][l]==1) try1(k-2,l);
if(l+2<m && a[k][l+2]=='#' && f[k][l+2]==1) try1(k,l+2);
if(l-2>=0&& a[k][l-2]=='#' && f[k][l-2]==1) try1(k,l-2);

if(k+1<n && l+1<m && a[k+1][l+1]=='#' && f[k+1][l+1]==1) try1(k+1,l+1);
if(k+1<n && l-1>=0&& a[k+1][l-1]=='#' && f[k+1][l-1]==1) try1(k+1,l-1);
if(k-1>=0&& l-1>=0&& a[k-1][l-1]=='#' && f[k-1][l-1]==1) try1(k-1,l-1);
if(k-1>=0&& l+1<m && a[k-1][l+1]=='#' && f[k-1][l+1]==1) try1(k-1,l+1);
}

int main()
{

cin>>n>>m;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
cin>>a[i][j];

for(i=0;i<n;i++)
for(j=0;j<m;j++)
f[i][j]=1;
s=0;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if(a[i][j]=='#'&&f[i][j]==1)
{
s++;
try1(i,j);
}
cout<<s;
return 0;

}

include <iostream>
using namespace std;

char a[100][100];
int f[100][100];
int n,m,i,j,s;
void try1(int k,int l)
{
f[k][l]=0;
if(k+1<n && a[k+1][l]=='#' && f[k+1][l]==1) try1(k+1,l);
if(k-1>=0&& a[k-1][l]=='#' && f[k-1][l]==1) try1(k-1,l);
if(l+1<m && a[k][l+1]=='#' && f[k][l+1]==1) try1(k,l+1);
if(l-1>=0&& a[k][l-1]=='#' && f[k][l-1]==1) try1(k,l-1);

if(k+2<n && a[k+2][l]=='#' && f[k+2][l]==1) try1(k+2,l);
if(k-2>=0&& a[k-2][l]=='#' && f[k-2][l]==1) try1(k-2,l);
if(l+2<m && a[k][l+2]=='#' && f[k][l+2]==1) try1(k,l+2);
if(l-2>=0&& a[k][l-2]=='#' && f[k][l-2]==1) try1(k,l-2);

if(k+1<n && l+1<m && a[k+1][l+1]=='#' && f[k+1][l+1]==1) try1(k+1,l+1);
if(k+1<n && l-1>=0&& a[k+1][l-1]=='#' && f[k+1][l-1]==1) try1(k+1,l-1);
if(k-1>=0&& l-1>=0&& a[k-1][l-1]=='#' && f[k-1][l-1]==1) try1(k-1,l-1);
if(k-1>=0&& l+1<m && a[k-1][l+1]=='#' && f[k-1][l+1]==1) try1(k-1,l+1);
}

int main()
{

cin>>n>>m;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
cin>>a[i][j];

for(i=0;i<n;i++)
for(j=0;j<m;j++)
f[i][j]=1;
s=0;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if(a[i][j]=='#'&&f[i][j]==1)
{
s++;
try1(i,j);
}
cout<<s;
return 0;

}

#include <iostream>
using namespace std;

char a[100][100];
int f[100][100];
int n,m,i,j,s;
void try1(int k,int l)
{
f[k][l]=0;
if(k+1<n && a[k+1][l]=='#' && f[k+1][l]==1) try1(k+1,l);
if(k-1>=0&& a[k-1][l]=='#' && f[k-1][l]==1) try1(k-1,l);
if(l+1<m && a[k][l+1]=='#' && f[k][l+1]==1) try1(k,l+1);
if(l-1>=0&& a[k][l-1]=='#' && f[k][l-1]==1) try1(k,l-1);

if(k+2<n && a[k+2][l]=='#' && f[k+2][l]==1) try1(k+2,l);
if(k-2>=0&& a[k-2][l]=='#' && f[k-2][l]==1) try1(k-2,l);
if(l+2<m && a[k][l+2]=='#' && f[k][l+2]==1) try1(k,l+2);
if(l-2>=0&& a[k][l-2]=='#' && f[k][l-2]==1) try1(k,l-2);

if(k+1<n && l+1<m && a[k+1][l+1]=='#' && f[k+1][l+1]==1) try1(k+1,l+1);
if(k+1<n && l-1>=0&& a[k+1][l-1]=='#' && f[k+1][l-1]==1) try1(k+1,l-1);
if(k-1>=0&& l-1>=0&& a[k-1][l-1]=='#' && f[k-1][l-1]==1) try1(k-1,l-1);
if(k-1>=0&& l+1<m && a[k-1][l+1]=='#' && f[k-1][l+1]==1) try1(k-1,l+1);
}

int main()
{

cin>>n>>m;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
cin>>a[i][j];

for(i=0;i<n;i++)
for(j=0;j<m;j++)
f[i][j]=1;
s=0;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if(a[i][j]=='#'&&f[i][j]==1)
{
s++;
try1(i,j);
}
cout<<s;
return 0;

}

点击查看程序源码+详细题解

floodfill可以秒过……

BFS

少些一个等号害我找了半天错= =

编译通过...

├ 测试数据 01：答案正确... (0ms, 268KB)

├ 测试数据 02：答案正确... (0ms, 304KB)

├ 测试数据 03：答案正确... (0ms, 304KB)

├ 测试数据 04：答案正确... (0ms, 328KB)

├ 测试数据 05：答案正确... (0ms, 340KB)

├ 测试数据 06：答案正确... (0ms, 268KB)

├ 测试数据 07：答案正确... (0ms, 268KB)

├ 测试数据 08：答案正确... (0ms, 268KB)

├ 测试数据 09：答案正确... (0ms, 308KB)

├ 测试数据 10：答案正确... (0ms, 888KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 0ms / 888KB

#include

using namespace std;

char a[100][100];

int f[100][100];

int n,m,i,j,s;

void try1(int k,int l)

{

f[k][l]=0;

if(k+1=0&& a[k-1][l]=='#' && f[k-1][l]==1) try1(k-1,l);

if(l+1=0&& a[k][l-1]=='#' && f[k][l-1]==1) try1(k,l-1);

if(k+2=0&& a[k-2][l]=='#' && f[k-2][l]==1) try1(k-2,l);

if(l+2=0&& a[k][l-2]=='#' && f[k][l-2]==1) try1(k,l-2);

if(k+1=0&& a[k-1][l-1]=='#' && f[k-1][l-1]==1) try1(k-1,l-1);

if(k-1>=0&& l+1>n>>m;

for(i=0;ia[i][j];

for(i=0;i

广度优先化搜索，但要注意的是队列的范围要尽量开大。

题简单，找到'#' 然后把同属于一个图案的点都删掉，再找下一个图就行，不过还是膜拜0ms大牛了……

点击这里查看

#include

#include

#include

#define MN 1000

char s[MN][MN];

int n, m,vis[MN][MN];

int dx[] = {-1, -1,-1, 0, 0, 1, 1, 1, -2, 0, 0, 2},

dy[] = {-1, 0, 1, -1, 1, -1, 0,1, 0, -2, 2, 0};

void dfs(int i, int j) {

if(s[i][j] == '-' || vis[i][j]) return;

vis[i][j] = 1;

for(int x = 0; x < 12; x++) {

int u = i + dx[x], v = j + dy[x];

if(u < n && u >= 0 && v < m && v >= 0)

if(!vis[v] && s[v] == '#')

dfs(u, v);

}

}

int main()

{

int ans = 0;

scanf("%d %d", &n, &m);

for(int i = 0; i < n; i++)

scanf("%s\n", s[i]);

for(int i = 0; i < n; i++)

for(int j = 0; j < m; j++)

if(!vis[i][j] && s[i][j] != '-') {

ans++; dfs(i, j);

}

printf("%d\n", ans);

return 0;

}

FLOODFILL 不是显然的吗,,,