POJ 1321碁盤問題

http://poj.org/problem?id=1321
标题:今まで見たPOJの2番目の中国語の問題と言ってもいいですか、中国語でもよく理解できる以上、詳しくは述べません
構想:典型的な深捜しDFS;
 

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std ;

const int maxn = 100 ;

int vis[maxn] ;

int ch[maxn][maxn] ;

int cnt = 0 ,n,k ;

int judge(int a,int b)//                            

{

    for(int i = 1 ; i <= n ; i++)

    {

        if(ch[a][i] == -1)

        return 0 ;

        if(ch[i][b] == -1)

        return 0 ;

    }

    return 1 ;

}

void dfs(int step,int col)//step      ，col           

{

    if(col == k)

    {

        cnt++ ;

        return ;

    }

    if(step == n*n)

    return ;

    int a = step/n+1 ;//            

    int b = step%n+1 ;

    if(ch[a][b]&&judge(a,b))//    #                # 

    {

        ch[a][b] = -1 ;//   #        

        dfs(step+1,col+1) ;

        ch[a][b] = 1 ;//           ，    ，      

    }

    dfs(step+1,col) ;//        ，               

    return ;

}

int main()

{

    while(~scanf("%d %d",&n,&k))

    {

        if(n == -1&&k == -1)

        break ;

        cnt = 0 ;

        char sh ;

        memset(ch,0,sizeof(ch)) ;

        for(int i = 1 ; i <= n ; i++)

        {

            for(int j = 1 ; j <= n ; j ++)

            {

                cin>>sh ;

                if(sh == '#')

                ch[i][j] = 1 ;//#   1         

            }

        }

        dfs(0,0) ;

        cout<<cnt<<endl ;

    }

}

View Code
 
 
これは優さんが書いたもので、簡潔明瞭で、
 

//Memory Time 

//184K   32MS 



#include<iostream>

using namespace std;



bool chess[9][9];

bool vist_col[9];  //   

int status;  //     

int n,k;



void DFS(int row,int num)  //    ，row      ，num        

{

    if(num==k)

    {

        status++;

        return;

    }



    if(row>n)    //    DFS(row+1,num);     ，      

        return;



    for(int j=1;j<=n;j++)

        if(chess[row][j] && !vist_col[j])

        {

            vist_col[j]=true;  //        

            DFS(row+1,num+1);

            vist_col[j]=false; //   ，            ，        

        }



    DFS(row+1,num);   //     ， k<n ，row   n              

                      //                              

                      //         ，          ，            

    return;

}



int main(int i,int j)

{

    while(cin>>n>>k)

    {

        if(n==-1 && k==-1)

            break;



        /*Initial*/



        memset(chess,false,sizeof(chess));

        memset(vist_col,false,sizeof(vist_col));

        status=0;



        for(i=1;i<=n;i++)

            for(j=1;j<=n;j++)

            {

                char temp;

                cin>>temp;

                if(temp=='#')

                    chess[i][j]=true;

            }



        DFS(1,0);  //           

        cout<<status<<endl;

    }

    return 0;

}

View Code