[白俊]1941で有名な七姫(ジャワ)

18305 ワード
有名な七姫 BFS boj ブルトポス Java コンポジット 白駿 ジャワ 1941 テキストリンク

質問する


全部で25人の女子学生で構成された女子学生のクラスは5です.×5の正方形の格子の位置が配置され、間もなく、李多順と林道妍の2人の学生が頭角を現し、他の学生を振り回し始めた.すぐに、すべての女子学生は「李多順派」と「林多燕派」の2派に分裂し、やがて「林多燕派」は勢力を拡大し、「李多順派」を脅かし始めた.
危機意識を感じた「李多順派」の学生たちは、今の体制を果敢に放棄し、「有名な七姫」の誕生が唯一の生存手段であることに気づいた.「有名な七姫」は以下のルールを満たすべきです.
名前は
  • なので、女子学生7人で構成されているはずです.
  • の強い凝集力を維持するために、7人の席は横に隣接しなければならない.
  • の調和と繁栄を実現するためには、必ずしも「李多順派」の学生だけで構成されるとは限らない.
  • しかし、生き残るためには「伊達ソム派」が優位に立たなければならない.このため、7人のうち少なくとも4人以上の「李多順派」が含まれなければならない.
    • 女子クラスの席の配置図をあげたら、「有名な七姫」を構成できるすべての場合の人数をプログラムに書きます.

    入力


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

    しゅつりょく


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

    I/O例



    に答える

  • 225箇所のうち7箇所を選択
    • .
  • 選択された7つの位置で、伊達ソム波が4より大きいかどうかを確認します.
  • 4以上であれば7箇所あることを確認してください.
  • 2,3の条件を満たす場合+1

    • コード#コード#

    import java.io.*;
import java.util.*;

public class Main {
	static char[][]arr = new char[5][5];
	static boolean[] visited = new boolean[25];
	static int[]selected=new int[7];
	static int[]dx= {1,-1,0,0};
	static int[]dy= {0,0,1,-1};
	static int answer=0;
	static void dfs(int depth,int start) {
		if(depth==7){
			if(check())answer++;
			return;
		}
		for(int i=start;i<25;i++) {
			if(!visited[i]) {	
				visited[i]=true;
				selected[depth]=i;
				dfs(depth+1,i+1);
				visited[i]=false;
			}
		}
	}
	static boolean check() {
		int Y=0;
		for(int i:selected) {
			if(arr[i/5][i%5]=='Y')Y++;
		}
		if(Y>3)return false;
		ArrayList<Integer>temp = new ArrayList<>();
		for(int a:selected)temp.add(a);
		
		Queue<Integer> q= new LinkedList<>();
		q.offer(selected[0]);
		while(!q.isEmpty()) {
			int i = q.poll();
			for(int d=0;d<4;d++) {
				int nx=i/5+dx[d];
				int ny=i%5+dy[d];
				if(nx>=0&&nx<5&&ny>=0&&ny<5){
					if(temp.contains(nx*5+ny)) {
						temp.remove(Integer.valueOf(nx*5+ny));
						q.offer(nx*5+ny);
					}
				}
			}
		}
		if(!temp.isEmpty())return false;
		return true;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for(int i=0;i<5;i++) {
			arr[i]=br.readLine().toCharArray();
		}
		dfs(0,0);
		System.out.println(answer);
	}
}
    TIL|[Spring]JPAについて
    ES 6新規加入内容(3)