AtCoder Regular Contest 031 B - 埋め立て

方針

・地図は10*10なので全探索可能
・埋め立てたときに複数の島を連結させられる海マスとは、少なくとも上下左右に二つの隣接した島マスを持っている必要がある
・地図を二次元配列に読み込む（このとき、島の総マス数を記録しておく。areaとする）
・上の条件を満たす海マスそれぞれについて、埋め立てて、深さ優先なり幅優先探索をし、探索できた島のマス数がarea+1であればYes。area+1を満たせなければNo。

import static java.lang.System.*;
import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	static char[][] map = new char[10][10];
	static int area;
	public static void main(String[] args) {

		//マップを作成。それと同時に、陸マスも数える
		for (int i=0; i<10; i++) {
			map[i] = sc.next().toCharArray();
			for (int j=0; j<10; j++) {
				if (map[i][j]=='o') area++;
			}
		}


		//変数とか
		int[] dx = {0,1,0,-1};
		int[] dy = {-1,0,1,0};
		boolean F = false;


		//メイン処理
		loop : for (int i=0; i<10; i++) {
			for (int j=0; j<10; j++) {

				//すべての海マスで全探索してもよいのだが、ここでは計算量を減らすため、
				//上下左右に合計で2個以上の陸マスと隣接している海マスを検出する
				int landNum = 0;
				if (map[i][j]=='x') {
					for (int k=0; k<4; k++) {
						int y = i + dy[k];
						int x = j + dx[k];
						if (y<0 || x<0 || y>9 || x>9) continue;
						if (map[y][x]=='o') landNum++;
					}

					//条件を満たす海マスであれば、再帰関数で陸地を探索
					if (landNum >= 2) {
						boolean[][] memo = new boolean[10][10];
						dfs(i,j,0,memo);
						int areaNum = 0;
						for (int k=0; k<10; k++) {
							for (int l=0; l<10; l++) {
								if (memo[k][l]) areaNum++;
							}
						}

						//埋め立てた海マスからすべての陸マスに行けるなら、trueにしてbreak
						if (areaNum == area+1) {
							F = true;
							break loop;
						}
					}
				}
			}
		}


		//出力
		out.println(F?"YES":"NO");
	}


	//陸地探索用の再帰関数。
	static void dfs(int sy, int sx, int n, boolean[][] memo) {
		if (sy<0 || sx<0 || sy>9 || sx>9 || memo[sy][sx]) return;
		//海マスから探索を始めるので、何もしないと呼び出し1回目で再帰関数が終了してしまう。
		//そのため以下の条件で、呼び出し1回目はたとえ海マスであっても処理を続行するようにした。
		if (n!=0 && map[sy][sx]=='x') return;
		memo[sy][sx] = true;
		dfs(sy-1,sx,n+1,memo);
		dfs(sy,sx+1,n+1,memo);
		dfs(sy+1,sx,n+1,memo);
		dfs(sy,sx-1,n+1,memo);
	}
}

提出してACがついてから気がついたのですが、このコードだと「陸地が1マスだけのとき」「陸地が最初から1つの島で、なおかつ直線状のとき」などが検出できません。島同士を繋ぐという問題ですし、陸地が必ず2つ以上の島に分かれていることを前提とするなら、このコードでも問題ないのかなとは思います。

もし上記の状態まで検出するなら、海マス検出の条件を削除し、素直に海マスを全探索すればよいと思います。