1217：棋盘问题

约定不等于承诺〃 2022-12-13 12:42 169阅读 0赞

1217：棋盘问题  
经典搜索问题  
时间限制: 1000 ms 内存限制: 65536 KB  
提交数: 8752 通过数: 4145  
【题目描述】  
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放 k 个棋子的所有可行的摆放方案 C。

【输入】  
输入含有多组测试数据。

每组数据的第一行是两个正整数n,k，用一个空格隔开，表示了将在一个n×n的矩阵内描述棋盘，以及摆放棋子的数目。 (n≤8,k≤n)  
当为−1−1时表示输入结束。

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

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

【输入样例】  
2 1  
\#.  
.\#  
4 4  
…\#  
…\#.  
.\#…  
\#…  
\-1 -1  
【输出样例】  
2  
1

## 思路： ##

1.每一行可能有摆放位置也可能没有摆放位置；  
2.每一行只能放一个棋子；  
**核心代码两个事例；**

char G[maxn][maxn];//图
    int dis[maxn];//dfs[i]:表示第i行选择的空位
    int n,k;//n:棋盘大小,K:棋子个数;
    long long sum = 0;//sum:摆放总数
    int shu[maxn];
    void search(int row,int y) {
        
    	if (y== k&&row<=n+1) {
        
    		sum++;
    		return;
    	}
    	else if (row > n)return;
    	for (int col = 1; col <= n; col++) {
        //搜索当前行是否有排放位置
    		if (shu[col] == 0 && G[row][col] == '#') {
        
    			shu[col] = 1;
    			dis[row] = col;
    			search(row + 1,y+1);
    			shu[col] = 0;
    		}
    	}
    	search(row + 1, y);//这一列没有进入下一列
    }

void dfs(int x, int y)//x:行，y:摆放棋子的个数和
    {
        
    	if (y == k)
    	{
        
    		sum++;
    		return;
    	}
    	for (int i = x; i <= n; i++)
    		for (int j = 1; j <= n; j++)
    			if (G[i][j] == '#' && shu[j]==0)
    			{
        
    				shu[j] = 1;
    				dfs(i + 1, y + 1);
    				shu[j] = 0;
    			}
    	return;
    }

int main() {
        
    	while (scanf_s("%d%d", &n, &k) != EOF) {
        
    		if (n == -1 && k == -1)
    			break;
    		//init:G,dis,n,k,sum
    		sum = 0;
    		for (int i = 1; i <= n; i++) {
        
    			dis[i] = 0; shu[i] = 0;
    			for (int j = 1; j <= n; j++) {
        
    				cin >> G[i][j];
    			}
    		}
    		search(1, 0);
    		/*
    		//或者
    		dfs(1,0);
    		*/
    		printf("%lld\n", sum);
    	}
    	return 0;
    }