碁盤問題POJ-1321

碁盤問題POJ−1321は、所定の形状の碁盤(形状が不規則である可能性がある)の上に駒を並べ、駒に違いはない.任意の2つの駒を碁盤の中の同じ行または同じ列に置くことができないことを要求する場合は、所定の形状と大きさの碁盤に対して、k個の駒を置くすべての実行可能な配置スキームCをプログラミングして解いてください.Input入力には複数のテストデータが含まれています.各グループのデータの最初の行は2つの正の整数、n kであり、1つのスペースで区切られ、1つのn*nのマトリクス内に碁盤を記述し、駒を置く数を示す.n<=8,k<=nは−1−1で入力終了を示す.次のn行は、各行にn文字を有する碁盤の形状を示す.空白領域を表します(データは余分な空白行や空白列が現れないことを保証します).Outputは、各セットのデータに対して、1行の出力を与え、配置されたシナリオ数Cを出力する(データ保証C<2^31).Sample Input 2 1 #. .# 4 4 …# …#. .#… #… -1 -1 Sample Output 2 1
構想:簡単な検索、dfs水問題、八皇后の問題に似ています.https://blog.csdn.net/h_666666/article/details/86748415以前書いたのですが、(dfsは遡るべきですが、ここの書くのと書かないのは確かに違います)、それから問題には「データは余分な空白行や空白列が現れないことを保証します.そうすれば、今何個の駒を置いているのかを判断するのを省くことができます.そしてvis配列も書いて、直接列をマークすればいいです.低軌道の次の行のため、したがって、ロー間で競合はありません.
もう一つ愚かなことがあって、題意を理解していないで、いったい#が放すことができるのか、それとも.入れられる???
下のACのコードはdfsの正规の操作に属して、板の话はやはり下のあれを选びます
最初のwa落ちのコードは、遡及を書いて、テストサンプルは通過できますが、wa落ち額???どなたか見て間違いを指摘してくれて、泣いて、、、

import java.util.Scanner;

class Main{
    static char[][] graph;
    static char[][] flag;
    static int n;
    static  int k;
    static int count;
    static int num;
    public static void main(String[] args) {
        Scanner sc  = new Scanner(System.in);
        while (true){
            n= sc.nextInt();
            k = sc.nextInt();
            if(n==-1 && k ==-1){
                break;
            }
            else {
                graph = new char[n][n];
                flag = new char[n][n];
                for(int i =0;i<n;i++){
                    graph[i] = sc.next().toCharArray();
                }
                count  = 0;
                num = 0;
                dfs(0,0);
                System.out.println(num);

            }
        }
    }
    static void dfs(int row,int count){
        if(count==k){
            num++;
            return;
        }
        for(int col = 0;col<n;col++){
            boolean cheack = true;
            for(int i =0;i<row;i++){
                if(flag[i][col]==1 || graph[row][col]=='.'){
                    cheack = false;
                    break;
                }
            }
            if(cheack){
                flag[row][col] = 1;
                dfs(row+1,count+1);
                flag[row][col] = 0;
            }
        }
    }


}

acコード:

import java.util.Scanner;

class Main{
    static int vis[] = new int[20];
    static char[][] graph = new char[20][20];
    static int n;
    static int k;
    static int num = 0;
    public static void main(String[] args) {
        Scanner sc  = new Scanner(System.in);
        while (true){
            n= sc.nextInt();
            k = sc.nextInt();
            if(n==-1 && k ==-1){
                break;
            }
            else {

                for(int i =0;i<n;i++){
                    graph[i] = sc.next().toCharArray();
                }
                num = 0;
                dfs(0,0);
                System.out.println(num);

            }
        }
    }
    static void dfs(int x,int y){
        if(y>=k){ //             ，    ｊ   ，  ｙ     ，        
            num++;
            return;
        }
        for(int i = x;i<n;i++){
            for(int j =0;j<n;j++){
                if(vis[j]==0 && graph[i][j]=='#'){
                    vis[j] = 1;
                    dfs(i+1,y+1);
                    vis[j] = 0;
                }
            }
        }
    }
}