20612统计八连块

50237242海岛帝国:神圣之日

【试题描述】

输入一个m行n列的字符矩阵,统计字符“@”组成多少个八连块。如果两个字符“@”所在的格子相邻(横竖或者对角线方向),就说它们属于同一个八连块。例如,下图中有两个八连块。

【输入要求】

第一行包括两个正整数m和n,由空格隔开,接下来的m行,每行n个字符,字符只包括“*”和“@”。

【输出要求】

一个数,表示八连块的个数

【输入实例】

5 5
****@
*@@*@
*@**@
@@@*@
@@**@

 

【输出实例】

2

【其他说明】

数据范围:0<m,n<101。LJX出品

【试题分析】

很经典的dfs,老师讲的是:一开始先进入图中,然后找到一个@,从此开始搜,如果不是,退回。这时当时刚刚接触dfs时的题,很简单。

【代码】

#include<iostream>
#include<cstring>
int mm[101][101],r[101][101];
void lk(int x, int y)
{
    if(!mm[x][y]||r[x][y]) return;
    r[x][y]=1;
    lk(x-1,y-1); //周围全搜一遍
	lk(x-1,y+1);
	lk(x+1,y-1);
	lk(x+1,y+1);
	lk(x-1,y);
	lk(x+1,y);
    lk(x,y-1);
	lk(x,y+1);
}
int main()
{
    int n,i,j,m,ans=0;
    char s[101];
    scanf("%d%d",&n,&m);
    for (i=0;i<n;i++)
    {
        memset(s,0,sizeof(s));
        scanf("%s",s);
        for (j=0;j<m;j++)//这里是把整个地图的记录移了一下,从0变成1了
        	if(s[j]==‘@‘)mm[i+1][j+1]=1;
            else mm[i+1][j+1]=0;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(!r[i][j]&&mm[i][j])
            {
                ans++;
                lk(i,j);
            }
    printf("%d\n",ans);
}  
时间: 06-25

20612统计八连块的相关文章

CNUOJ 0079 20612统计八连块

20612统计八连块 难度级别:B: 运行时间限制:1000ms: 运行空间限制:51200KB: 代码长度限制:2000000B 试题描述 输入一个m行n列的字符矩阵,统计字符“@”组成多少个八连块.如果两个字符“@”所在的格子相邻(横竖或者对角线方向),就说它们属于同一个八连块.例如,下图中有两个八连块.                         输入 第一行包括两个正整数m和n,由空格隔开,接下来的m行,每行n个字符,字符只包括“*”和“@”. 输出 一个自然数,表示八连块的个数.

黑白图像—————— 八连块

八连块 [题目]:              输入一个n*n的黑白图像(1表示黑色,0表示白色),任务是统计其中八连块的个数.如果两个黑格子有        公共边或者公共顶点,就说它们属于同一个八连块.如下图6-11表示3个八连块. [分析]             通过题目要求,定义8方向数组,运用搜索来确定有几个八连块,搜索查找,     查找过的进行标记,保证不会重复查找到原来的黑格子,另外还要考虑边界问           题,但是下面我的方法就不用考虑边界问题,认真看下面就知道方法了

紫书p199 八连块(BFS,hash)

八连块问题  紫书上的简单搜索  渣渣好久才弄懂 #include<cstdio> #include<cstring> using namespace std; const int M = 1000003; int x[4] = { -1, 1, 0, 0}, y[4] = {0, 0, -1, 1}; int dis[M], h[M], s[M][9], e[9]; int aton(int a[]) { int t = 0; for(int i = 0; i < 9; +

八连块

1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int MAX = 100; 5 char arr[MAX][MAX]; 6 int n,m; 7 8 void init(); 9 void solve(); 10 void dfs(int x,int y); 11 12 void init(){ 13 cin>>n>>m;//输入行数列数 14 for(int i=0;i<n;i++){ 1

八连块问题:统计图中相相连黑色区域的个数

一个n*n个方块的图,每个方块是白色或者黑色.统计出相连的黑色块区域有多少个 相连:两个黑色块有公共顶点或者公共边输入0代表白色 1代表黑色 测试用例: 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 1 0 1 0 0 答案: 有三块相连的黑色区域 python实现: 1 ''' 2 对每方块进行遍历: 3 1 如果值是0或者-1 不进行操作 4 2 如果值是1 把值改为-1 标记一下 已经遍历过这个点 5 2.2 把

foodfill 八连块问题

Description Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer

八连块问题

问题描述:共有多少块相邻的空白的区域 注意递归和边界问题的值的设置 源代码如下: #include<stdio.h> #include<stdlib.h> #include<string.h> #define MAX 100 +10 using namespace std; int mat[MAX][MAX] ,vis[MAX][MAX]; void dfs(int x,int y) { if(!mat[x][y] || vis[x][y]) //1代表空白 retur

UVA 572 Oil Deposits油田(DFS求连通块)

UVA 572     DFS(floodfill)  用DFS求连通块 Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u Description Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M

DFS入门之二---DFS求连通块

用DFS求连通块也是比较典型的问题, 求多维数组连通块的过程也称为--“种子填充”. 我们给每次遍历过的连通块加上编号, 这样就可以避免一个格子访问多次.比较典型的问题是”八连块问题“.即任意两格子所在位置相邻(上下左右对角共八个方位),则在一个连通块.典型例题:HDU 1241 Oil Deposits 传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1241 题目描述:输入m行n列的字符矩阵, 统计字符“@”组成八连块的个数. 题意分析:读入数据