Balloons(DFS)
2024-08-24 19:50:51
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2248
题意:(1)求图中四连块(有公共边的方块)的个数;
(2)求图中八连块(有公共顶点的方块)的个数。
#include<stdio.h>
#include<string.h>
const int N = ;
int vis1[N][N],map[N][N],vis[N][N];
void dfs1(int x,int y)//搜索四个方向
{
if (!map[x][y]||vis1[x][y])
return ;
vis1[x][y] = ;
dfs1(x-,y);
dfs1(x+,y);
dfs1(x,y-);
dfs1(x,y+);
}
void dfs(int x,int y)//搜索八个方向
{
if(!map[x][y]||vis[x][y])
return ;
vis[x][y] =;
dfs(x-,y-);dfs(x-,y);dfs(x-,y+);
dfs(x,y-); dfs(x,y+);
dfs(x+,y-);dfs(x+,y);dfs(x+,y+); }
int main()
{
int n,i,j,o = ;
char s[N];
while(~scanf("%d",&n)&&n)
{
++o;
int cnt1 = ;
int cnt2 = ;
memset(vis1,,sizeof(vis));
memset(vis,,sizeof(vis));
memset(map,,sizeof(map));
for (i = ; i < n; i ++)
{
scanf("%s",s);
for (j = ; j < n; j ++)
{
map[i+][j+] = s[j]-'';//在图周围加一圈空格,防止判断时越界
}
}
for (i = ; i <= n; i ++)
{
for (j = ; j <= n; j ++)
{
if (map[i][j]&&!vis1[i][j])
{
cnt1++;
dfs1(i,j); }
if (map[i][j]&&!vis[i][j])
{
cnt2++;
dfs(i,j);
} }
}
printf("Case %d: %d %d\n\n",o,cnt1,cnt2);
}
return ;
}
最新文章
- [Android]Android MVP&;依赖注入&;单元测试
- Java多线程系列--“JUC集合”07之 ArrayBlockingQueue
- mysql5.6源码安装
- python 字符串复制
- 【poj 2185】Milking Grid(字符串--KMP+问题分解)
- 【CocoaPods】配置CocoaPods前 - 本地安装好Ruby环境
- Coursera《machine learning》--(6)逻辑回归
- linux是一种修行
- github使用及代码同步
- SimpleDateFormat日期格式(浅面)
- Spring Boot中采用Mockito来mock所测试的类的依赖(避免加载spring bean,避免启动服务器)
- ABP官方文档翻译 5.1 Web API控制器
- Windows安装SVN服务器和客户端
- 第1章-Struts2 概述 --- Struts2和MVC
- Java 读书笔记 (十四) Java 方法
- C语言实现将日期、时间保存到文本文件中
- hive数据导出到本地目录 抛异常
- 3种PHP连接MYSQL数据库的常用方法
- 【Asp.net入门15】第一个Asp.net应用程序-输入验证
- vsCode开发java遇到的问题整理、解决方案(持续更新)
热门文章
- ECC 构筑安全可靠的区块链
- docker安装后出现Cannot connect to the Docker daemon
- Python 模块的导入 day5
- Day 13 进程和线程
- python编写webservice接口
- Python3:numpy模块中的argsort()函数
- forcedirectories和CreateDirectory
- mapbox-gl 使用ArcGISServer 发布的栅格切片
- 获取springbean的几种方式
- Bitvise ssh client+ chrome +SwitchyOmega *** (xjl456852原创)