// 0067:The Number of Island
#include <iostream>
#include <string>
using namespace std;
const int size_y=10;
const int size_x=10;
class Atlas {
string map_[size_y][size_x];
public:
Atlas() {}
Atlas( string const (&map)[size_y][size_x] ) {
for ( int y = 0; y != size_y; ++y ) {
for ( int x = 0; x != size_x; ++x ) {
map_[y][x] = map[y][x];
}
}
}
string operator ()( int x, int y ) const { return map_[y][x]; }
string &operator() ( int x, int y ) { return map_[y][x]; }
};
bool outofRange( int x, int y ) {
return x < 0 || size_x <= x || y < 0 || size_y <= y;
}
struct Move {
int x;
int y;
};
int check( Atlas const &atlas, int x, int y, Atlas &island ) {
static Move const move[] = { {0,-1}, {1,0}, {0,1}, {-1,0} };
if ( atlas( x, y ) == " " ) return 0; // 移動不能ポイントなら何もせずリターン
island( x, y ) = "#"; // 今ここに来たことをチェック
// 次のポイントへ移動
int islandSize = 1;
for ( int i = 0; i != 4; ++i ) {
int xx = x + move[i].x;
int yy = y + move[i].y;
if ( outofRange( xx, yy ) ) continue; // Mapの外に出るようなスルー
if ( island( xx, yy ) == "#" ) continue; // すでにチェック済みならスルー
islandSize += check( atlas, xx, yy, island );
}
return islandSize; // 四方向すべてチェックしたなら終わり
}
void print_map( Atlas const &atlas ) {
for ( int y = 0; y != size_y; ++y ) {
for ( int x = 0; x != size_x; ++x ) {
cout << atlas( x, y );
}
cout << "\n";
}
cout << "\n";
}
int countIsland( Atlas const &atlas ) {
Atlas island;
int n = 0; // 島の数
for ( int i = 0; i < size_x * size_y; ++i ) {
int x = i % size_x;
int y = i / size_y;
if ( island( x, y ) == "#" ) continue; // チェック済みならスルー
if ( check( atlas, x, y, island ) ) ++n;
}
return n;
}
int main() {
string map[size_y][size_x]={
{" "," "," "," "," ","#"," "," ","#","#"},
{" "," "," "," "," "," ","#"," ","#","#"},
{" "," "," ","#","#","#"," ","#"," "," "},
{" "," ","#","#"," ","#"," "," "," "," "},
{" "," "," ","#"," "," ","#"," "," "," "},
{" "," "," "," "," "," "," "," "," ","#"},
{" "," "," "," ","#"," "," "," "," "," "},
{" "," ","#"," "," ","#"," "," "," ","#"},
{" "," ","#","#"," ","#"," "," "," ","#"},
{"#"," "," "," "," "," "," "," "," "," "}};
print_map(map);
Atlas atlas( map );
cout << countIsland( atlas ) << "\n";
return 0;
}