[ create a new paste ] login | about

Link: http://codepad.org/yLSJHvP9    [ raw code | output | fork ]

C++, pasted on Dec 11:
//	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;
}


Output:
1
2
3
4
5
6
7
8
9
10
11
12
     #  ##
      # ##
   ### #  
  ## #    
   #  #   
         #
    #     
  #  #   #
  ## #   #
#         

12


Create a new paste based on this one


Comments: