dfs入门-cogs1640[黑白图像]
2024-09-04 10:19:18
题目链接:http://cogs.pro:8081/cogs/problem/problem.php?pid=vxSmxkeqa
【题目描述】
输入一个n×n的黑白图像(1表示黑色,0表示白色),任务是统计其中八连块的个数。如果两个黑格子有公共边或者公共顶点,就说它们属于同一个八连块。如下图所示的图形有3个八连块。
【输入格式】
第1行输入一个正整数n(n≤700),此后输入n行,每行是由n个0或1组成的字符串。
【输出格式】
在此键入。
【样例输入】
6
100100
001010
000000
110000
111000
010100
【样例输出】
3
思路:以二维int数组存入整张图,设置vis数组表示当前位置是否访问过,读入时一定要以%1d读入,
因为一次只读一个,算法开始时将数组初始化为0,之后二层for循环遍历每个位置,如果vis为0且数据为1,
则进入dfs函数,每次访问将vis[i][j]赋值为1,搜索完ans++,最后结束循环。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std; int N;
int ans = ;
int c[][] = { };
int vis[][] = { };
int X[] = { , , -, , , -, , -};
int Y[] = { , , , -, -, , , -}; void dfs(int x, int y)
{
if (!c[x][y] || vis[x][y])
return;
vis[x][y] = ;
for (int i = ; i < ; i++)
{
int dx = x + X[i], dy = y + Y[i];
dfs(dx, dy);
}
} int main()
{
freopen("common.in", "r", stdin);
freopen("common.out", "w", stdout);
memset(c, , sizeof(c));
memset(vis, , sizeof(vis));
scanf("%d", &N);
getchar();
for (int i = ; i <= N; i++)
{
for (int j = ; j <= N; j++)
{
scanf("%1d", &c[i][j]);
}
getchar();
} for (int i = ; i <= N; i++)
{
for (int j = ; j <= N; j++)
{
if (!vis[i][j] && c[i][j])
{
ans++;
dfs(i, j);
}
}
}
printf("%d\n", ans);
return ;
}
最新文章
- WPF直接用Window.Close直接关闭窗口导致不能完全退出的问题
- LeetCode刷题系列
- MSSQL跨服务器插入
- js获取网页屏幕可视区域高度
- js的一点
- WM8978和VS1053B的区别
- iphone field test 源码
- Bootstrap 表格
- 百度地图 IOS版开发经验分享
- Conjugate prior relationships
- basicjava
- linux 学习之九、Linux 磁盘与文件系统管理(1)
- php 与redis 结合 使用predis
- JZ2440学习笔记之第一个裸机程序(Keil-MDK)
- shell 脚本加密
- HTML语言字符编码
- 跟随我在oracle学习php(3)
- Flash and Scalform CLIK
- C#正则_取出标签内的内容(非贪婪)
- maven中net.sf.json报错的解决方法(转载)