NCSTOJ-1499 : 国际象棋

短命女 2022-03-07 06:38 168阅读 0赞

# [1499 : 国际象棋][1499 _] #

### Description ###

国际象棋棋盘由黑白相间的格子组成，要把k个相同的棋子摆放在黑色区域内，摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列。

求对于给定的棋盘，摆放k个棋子的所有可行的摆放方案数。

### Input ###

输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开：n表示将在一个n\*n的矩阵内描述棋盘，k表示摆放棋子的数目。（ 1 ≤ k ≤ n ≤ 8 ）

随后的n行描述了棋盘的形状：每行有n个字符，其中 “\#” 表示黑色区域（可以摆放棋子）， “.” 表示白色区域（不可以摆放棋子）。（数据保证不出现多余的空白行或者空白列）。

当n k 为-1 -1时表示输入结束。

对于样例1:棋盘\[0,0\]\[1,1\]两个位置都可以摆放棋子，要把1个棋子摆放在这两个位置，共2种方案。

对于样例2:棋盘\[0,3\]\[1,2\]\[2,1\]\[3,0\]四个位置都可以摆放棋子，要把4个棋子摆放在这四个位置，共1种方案

### Output ###

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。

### Sample Input ###

2 1
    #.
    .#
    4 4
    ...#
    ..#.
    .#..
    #...
    -1 -1

### Sample Output ###

2
    1

### dis 回溯 ###

#include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<string>
    #include<cstring>
    #include<unordered_set>
    #include<set>
    #include<unordered_map>
    #include<vector>
    #include<algorithm>
    #include<set>
    #include<queue>
    #include<cmath>
    using namespace std;
    int n,k;
    char mp[10][10];
    int book[10];//表示第i行的第book[i]列
    int ans;
    void Backtrack(int x,int t) //x行，t个棋子 
    { 
        if(x>n) return;
        if(t==k)
        { 
            ans++;
            return;
        }
        for(int i=x;i<n;i++) //第i行从x开始
        { 
            for(int j=0;j<n;j++) //第j列
            { 
                if(mp[i][j]=='#'&&book[j]==0)
                { 
                    book[j]=1; //第i列被放置棋子，标记
                    Backtrack(i+1,t+1); //搜索下一行，棋子数加1
                    book[j]=0; //复原
                } 
            }
            //Backtrack(x+1,t);
        }
    }
    int main()
    { 
        while(scanf("%d%d",&n,&k)==2&&n!=-1&&k!=-1)
        { 
            for(int i=0;i<n;i++)
            { 
                scanf("%s",mp[i]);
            }
            ans = 0;
            memset(book,0,sizeof(book));
            //for(int i=0;i<n;i++)
            Backtrack(0,0); //表示从第i行开始放置棋子
            printf("%d\n",ans);
        }
        return 0;
    }

#include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<string>
    #include<cstring>
    #include<unordered_set>
    #include<set>
    #include<unordered_map>
    #include<vector>
    #include<algorithm>
    #include<set>
    #include<queue>
    #include<cmath>
    using namespace std;
    int n,k;
    char mp[10][10];
    int book[10];//表示第i行的第book[i]列
    int ans;
    void Backtrack(int x,int t) //x行，t个棋子 
    { 
        if(x>n) return;
        if(t==k)
        { 
            ans++;
            return;
        }
        for(int i=0;i<n;i++)
        { 
            if(mp[x][i]=='#'&&book[i]==0)
            { 
                book[i]=1;
                Backtrack(x+1,t+1);
                book[i]=0;
            }
        } 
        Backtrack(x+1,t);
    }
    int main()
    { 
        while(scanf("%d%d",&n,&k)==2&&n!=-1&&k!=-1)
        { 
            for(int i=0;i<n;i++)
            { 
                scanf("%s",mp[i]);
            }
            ans = 0;
            memset(book,0,sizeof(book));
            //for(int i=0;i<n;i++)
            Backtrack(0,0); //表示从第i行开始放置棋子
            printf("%d\n",ans);
        }
        return 0;
    }

[1499 _]: http://acm.ncst.edu.cn/problem.php?pid=1499