试题请參见: https://vijos.org/p/1051
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;
}原文：http://www.cnblogs.com/yxwkf/p/5246501.html