Surrounding Area - kyoupuro @ ウィキ

2014 : Surrounding Area

問題文

解説

杭が囲む領域を出力する。
左上から要素を見ていき、杭が見つかったら再帰を呼び出す。
再帰関数で、まだ塗られてない部分に色を塗っていく。すでに違う色で塗られていた場合は白黒以外で塗る。
最後に、塗った箇所を数え上げる。

プログラム

C

C++

対応するregion、endregionプラグインが不足しています。対になるようプラグインを配置してください。

#include<iostream>
using namespace std;

char map[51][51];
int w,h;
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};


void search(int x,int y,char c){

for(int i = 0; i < 4; i++){
	if(x+dx[i] < w && x+dx[i] >= 0 && y+dy[i] < h && y+dy[i] >= 0){
			if(map[y+dy[i]][x+dx[i]] == '.'){
				map[y+dy[i]][x+dx[i]] = c;
				search(x+dx[i],y+dy[i], c);
			}else if((map[y+dy[i]][x+dx[i]] == 'w' && c == 'b') || (map[y+dy[i]][x+dx[i]] == 'b' && c == 'w')){
			map[y+dy[i]][x+dx[i]] = '#';
				search(x+dx[i],y+dy[i], c);
			}
			
		}
	}	

	return;

}

int main(){

	while(cin >> w >> h,w||h){

		for(int i = 0; i < h; i++){
			cin >> map[i];
		}

		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				if(map[i][j] == 'W'){
					search(j,i,'w');
				}
				if(map[i][j] == 'B'){					
					search(j,i,'b');
				}
			}
		}

		int cw = 0, cb = 0;
		for(int i = 0; i < h; i++){
			for (int j = 0; j < w; j++) {
				if (map[i][j] == 'w') cw++;
				if (map[i][j] == 'b') cb++;
			}
	}

		cout << cb << ' ' << cw << endl;
	}
	return 0;
}

Java

解説と方法が違います。
→入力されたマップから黒白どちらかの土地になりうる'.'を探し、そこから繋がっている面積を1140番と同じ方法（見終わった場所を#に変える）で数え上げる。
その途中でBの杭が見つかった場合はboolean型変数Blackをtrueに、Wの場合はWhiteをtrueにする。
数え上げが終了したときにBlackのみtrueの場合は数え上げた面積はBlackの面積に加算し、Whiteのみtrueの場合はWhiteの面積に加算する。
BlackとWhiteが同じ場合はどちらの土地でもない。加算終了後、再びマップから'.'を探し数え上げする。

対応するregion、endregionプラグインが不足しています。対になるようプラグインを配置してください。

import java.util.Scanner;
public class SurroundingArea2014 {
static char[][] map;
static boolean Black,White;
static int w,h,count;
static void BlackOrWhite(int y,int x){
	if(map[y][x]=='W') White=true;
	if(map[y][x]=='B') Black=true;
}
static void move(int y,int x){
	map[y][x]='#';
	count++;
	if(0<y){
		BlackOrWhite(y-1,x);
		if(map[y-1][x]!='#'&&map[y-1][x]!='W'&&map[y-1][x]!='B') move(y-1,x);//↑
	}
	if(x<w-1){
		BlackOrWhite(y,x+1);
		if(map[y][x+1]!='#'&&map[y][x+1]!='W'&&map[y][x+1]!='B') move(y,x+1);//→			
	}
	if(0<x){
		BlackOrWhite(y,x-1);
		if(map[y][x-1]!='#'&&map[y][x-1]!='W'&&map[y][x-1]!='B') move(y,x-1);//←
	}
	if(y<h-1){
		BlackOrWhite(y+1,x);
		if(map[y+1][x]!='#'&&map[y+1][x]!='W'&&map[y+1][x]!='B') move(y+1,x);//↓
	}
}
public static void main(String[] args){
	Scanner scan=new Scanner(System.in);
	while(true){
		w=scan.nextInt(); h=scan.nextInt();
		if(w==0&&h==0){
			break;
		}else{
			map=new char[h][w];
			for(int i=0;i<h;i++){
				String s=scan.next();
				for(int j=0;j<w;j++){
					map[i][j]=s.charAt(j);
				}
			}
			int ans1=0;
			int ans2=0;
			for(int i=0;i<h;i++){
				for(int j=0;j<w;j++){
					Black=false; White=false;
					count=0;
					if(map[i][j]=='.'){
						move(i,j);
						if(Black&&!White) ans1+=count;
						if(!Black&&White) ans2+=count;
					}
				}
			}
			System.out.println(ans1+" "+ans2);
		}
	}
}
}