试题请參见: https://vijos.org/p/1051
题目概述
圣诞老人回到了北极圣诞区, 已经快到12点了. 也就是说极光表演要開始了. 这里的极光不是极地特有的自然极光景象. 而是圣诞老人主持的人造极光.
轰隆隆……烟花响起（来自中国的浏阳花炮之乡）. 接下来就是极光表演了.
人造极光事实上就是空中的一幅幅n*m的点阵图像. 仅仅是由于特别明亮而吸引了非常多非常多小精灵的目光, 也成为了圣诞夜最漂亮的一刻.
然而在每幅n*m的点阵图像中, 每个点仅仅有发光和不发光两种状态. 对于全部的发光的点, 在空中就形成了漂亮的图画. 而这个图画是以若干个（s个）图案组成的. 对于图案, 圣诞老人有着严格的定义：对于两个发光的点, 假设他们的曼哈顿距离（对于A(x1,y1)和B(x2,y2), A和B之间的曼哈顿距离为|x1-x2|+|y1-y2|）小于等于2. 那么这两个点就属于一个图案……
小精灵们一边赞赏着极光, 一边数着每一幅极光图像中的图案数. 伴着歌声和舞蹈, 度过了漂亮的圣诞之夜. ^_^
轰隆隆……烟花响起（来自中国的浏阳花炮之乡）. 接下来就是极光表演了.
人造极光事实上就是空中的一幅幅n*m的点阵图像. 仅仅是由于特别明亮而吸引了非常多非常多小精灵的目光, 也成为了圣诞夜最漂亮的一刻.
然而在每幅n*m的点阵图像中, 每个点仅仅有发光和不发光两种状态. 对于全部的发光的点, 在空中就形成了漂亮的图画. 而这个图画是以若干个（s个）图案组成的. 对于图案, 圣诞老人有着严格的定义：对于两个发光的点, 假设他们的曼哈顿距离（对于A(x1,y1)和B(x2,y2), A和B之间的曼哈顿距离为|x1-x2|+|y1-y2|）小于等于2. 那么这两个点就属于一个图案……
小精灵们一边赞赏着极光, 一边数着每一幅极光图像中的图案数. 伴着歌声和舞蹈, 度过了漂亮的圣诞之夜. ^_^
输入
第一行, 两个数n和m.
接下来一共n行, 每行m个字符. 对于第i行第j个字符, 假设其为“-”, 那么表示该点不发光, 假设其为“#”, 那么表示该点发光. 不可能出现其它的字符.
接下来一共n行, 每行m个字符. 对于第i行第j个字符, 假设其为“-”, 那么表示该点不发光, 假设其为“#”, 那么表示该点发光. 不可能出现其它的字符.
输出
第一行, 一个数s.
解题思路
Reference: http://chengchen2008.blog.163.com/blog/static/2834647520097207256587/
深度优先搜索
① 两个二维布尔数组: 用于存储地图和遍历记录
② 寻找每一个坐标
③ 对于每一个坐标。推断
o
o o o
o o # o o
o o o
o
以#为中心，推断以上几个位置（“o”）
若map[i][j]和used[i][j]都为真, 则继续在那个点进行深搜, 每搜索到一个点, 把那个点(use[i][j])置为false
遇到的问题
写之前还记得的, 写着写着就忘了.
小心数组下标越界啊~!! 递归调用的时候记得推断边界.
源码
#include <iostream>
#include <fstream> const int SIZE = 100; bool graph[SIZE][SIZE] = {0};
bool used[SIZE][SIZE] = {0}; void getNeighborPoint(int i, int j, int n, int m) {
if ( i < 0 || j < 0 || i >= n || j >= m ) {
return;
}
if ( graph[i][j] && !used[i][j] ) {
used[i][j] = true;
getNeighborPoint(i - 2, j, n, m);
getNeighborPoint(i - 1, j - 1, n, m);
getNeighborPoint(i - 1, j, n, m);
getNeighborPoint(i - 1, j + 1, n, m);
getNeighborPoint(i, j - 2, n, m);
getNeighborPoint(i, j - 1, n, m);
getNeighborPoint(i, j + 1, n, m);
getNeighborPoint(i, j + 2, n, m);
getNeighborPoint(i + 1, j - 1, n, m);
getNeighborPoint(i + 1, j, n, m);
getNeighborPoint(i + 1, j + 1, n, m);
getNeighborPoint(i + 2, j, n, m);
}
} int main() {
using std::cin;
// std::ifstream cin;
// cin.open("input.txt"); int n = 0, m = 0;
int numberOfGraphs = 0; // Input
cin >> n >> m;
for ( int i = 0; i < n; ++ i ) {
for ( int j = 0; j < m; ++ j ) {
char point = 0;
cin >> point;
graph[i][j] = ( point == '#' ? true : false );
}
} // Processing
for ( int i = 0; i < n; ++ i ) {
for ( int j = 0; j < m; ++ j ) {
if ( graph[i][j] && !used[i][j] ) {
getNeighborPoint(i, j, n, m);
++ numberOfGraphs;
}
}
} // Output
std::cout << numberOfGraphs << std::endl; return 0;
}