[白俊]#1941有名な七姫

16933 ワード
combination DFS algorithm 白駿 テキストリンク

質問する


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

    入力


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

    しゅつりょく


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

    入力例1

    YYYYY
SYSYS
YYYYY
YSYYS
YYYYY

    サンプル出力1

    2

    に答える


    この問題はbfs(幅優先探索)アルゴリズムで解くことができる.
    import java.io.InputStreamReader;
import java.io.BufferedReader;

public class Main {
    static int ans = 0;
    static int flag;
    static char[][] map;
    static int[] dx = {-1, 1, 5, -5};         //좌표 왼, 오, 아래, 위

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        map = new char[5][5];

        for(int i=0; i<5; i++) {
            String input = br.readLine();
            for(int j=0; j<5; j++)
                map[i][j] = input.charAt(j);
        }

        dfs(0, 0, 0, new boolean[25]);

        System.out.println(ans);
    }

    public static void dfs(int idx, int cnt1, int cnt2, boolean[] visited) {
        if(cnt1+cnt2==7) {                        //7개 선택 했을 때
            if(cnt1>cnt2) {                       //이다솜파가 더 많을 때
                flag = 1;

                boolean[] v = new boolean[25];
                v[idx-1] = true;
                check(idx-1, visited, v);

                if(flag==7)
                    ans++;
            }
            return;
        }

        for(int i=idx; i<25; i++) {                 //조합 선택
            if(!visited[i]) {
                visited[i] = true;

                if(map[i/5][i%5]=='S')
                    dfs(i+1, cnt1+1, cnt2, visited);
                else
                    dfs(i+1, cnt1, cnt2+1, visited);

                visited[i] = false;
            }
        }
    }

    public static void check(int idx, boolean[] visited, boolean[] v) {         //선택된 좌표들이 이어져 있는 지 확인

        for(int i=0; i<4; i++) {
            if((idx%5==0 && i==0) || (idx%5==4 && i==1)) continue;

            int ndx = idx+dx[i];

            if(ndx<0 || ndx>=25 || !visited[ndx] || v[ndx]) continue;

            v[ndx] = true;
            flag++;
            check(ndx, visited, v);
        }
    }
}
    白準2606ウイルス
    escape