[BOJ]1941有名な七姫

1941年に有名な七姫

難易度:金貨3
タイプ:コンビネーション、DFS、BFS、backtracking
https://www.acmicpc.net/problem/1941

質問する

全部で25人の女子学生で構成された女子学生のクラスは5です.×5の正方形の格子の位置が配置され、間もなく、李多順と林道妍の2人の学生が頭角を現し、他の学生を振り回し始めた.すぐに、すべての女子学生は「李多順派」と「林多燕派」の2派に分裂し、やがて「林多燕派」は勢力を拡大し、「李多順派」を脅かし始めた.
危機意識を感じた「李多順派」の学生たちは、今の体制を果敢に放棄し、「有名な七姫」の誕生が唯一の生存手段であることに気づいた.「有名な七姫」は以下のルールを満たすべきです.
名前は

なので、女子学生7人で構成されているはずです.

の強い凝集力を維持するために、7人の席は横に隣接しなければならない.

の調和と繁栄を実現するためには、必ずしも「李多順派」の学生だけで構成されるとは限らない.

しかし、生き残るためには「伊達ソム派」が優位に立たなければならない.このため、7人のうち少なくとも4人以上の「李多順派」が含まれなければならない.

女子クラスの席の配置図をあげたら、「有名な七姫」を構成できるすべての場合の人数をプログラムに書きます.

入力

「S」(「SOM」派の学生を表す)または「Y」(「任度」派の学生を表す)を値とする5*5行列には、1行目から5行目までの空白はありません.

しゅつりょく

1行目には「有名な七姫」を構成できるすべての状況の数字が出力されます.

に答える

最初は、BFSで隣接する7つの格子を検索して、4つのルールが満たされているかどうかを確認しましたが、T字型のパーティーは検索できないことがわかりました.
地図の大きさは5*5に固定されているので、25因子の中からランダムに7個の組み合わせを抽出してもよいし、7個の組み合わせを作成し、この組み合わせが4個以上ある場合にのみ、bfs検索により7個が隣接しているか否かを判断する.

コード#コード#

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

/**
 * BOJ_1941_G3_소문난 칠공주
 * @author mingggkeee
 * 조합,DFS,BFS,백트래킹
 */

public class BOJ_1941 {
	
	static class Location {
		int r, c;

		Location(int r, int c) {
			this.r = r;
			this.c = c;
		}
		
	}
	
	static char[][] map;
	static boolean[] isVisited;
	static int answer;
	static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
	
	static void combi(int cnt, int start, int y) {
		if (cnt == 7) {
			if (bfs())
				answer++;
			return;
		} 
		
		for (int i = start; i < 25; i++) {
			if (map[i / 5][i % 5] == 'Y' && y + 1 < 4) {
				isVisited[i] = true;
				combi(cnt + 1, i + 1, y + 1);
				isVisited[i] = false;
			}
			if (map[i / 5][i % 5] == 'S') {
				isVisited[i] = true;
				combi(cnt + 1, i + 1, y);
				isVisited[i] = false;
			}
		}
		
	}

	
	static boolean bfs() {
		Queue<Location> queue = new LinkedList<>();
		boolean[][] check = new boolean[5][5];
		
		for(int i = 0; i<25; i++) {
			if(isVisited[i]) {
				check[i / 5][i % 5] = true;
				queue.offer(new Location(i / 5, i % 5));
				break;
			}
		}
		
		int count = 1;
		
		while(!queue.isEmpty()) {
			Location now = queue.poll();
			for(int i = 0; i<4; i++) {
				int nr = now.r + dir[i][0];
				int nc = now.c + dir[i][1];
				if(nr < 0 || nr >= 5 || nc < 0 || nc >= 5) continue;
				if(!isVisited[nr * 5 + nc] || check[nr][nc]) continue;
				check[nr][nc] = true;
				queue.offer(new Location(nr, nc));
				count++;
			}
		}
		
		if(count == 7)
			return true;

		return false;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		map = new char[5][5];
		isVisited = new boolean[25];
		for (int i = 0; i < 5; i++) {
			String input = br.readLine();
			map[i] = input.toCharArray();
		}
		combi(0, 0, 0);
		System.out.println(answer);
	}
}