当前位置：网站首页>POJ1321 chessboard problem (detailed explanation)

POJ1321 chessboard problem (detailed explanation)

2022-07-30 04:37:00 【_rosy】

Title

Place chess pieces on a board of a given shape (the shape may be irregular) with no difference between the pieces.It is required that any two chess pieces cannot be placed in the same row or the same column in the chessboard. Please program to solve all feasible placement schemes C for placing k chess pieces for a chessboard of a given shape and size.

Input

The input contains multiple sets of test data.
The first line of each set of data is two positive integers, n k, separated by a space, indicating that the chessboard will be described in an n*n matrix and the number of pieces placed.n <= 8 , k <= n
When it is -1 -1, it means the end of input.
The next n lines describe the shape of the chessboard: each line has n characters, where # represents the chessboard area and . represents the blank area (the data guarantees that no extra blank rows or columns will appear).

Output

For each set of data, give a line of output, and output the number of solutions C (data guarantee C<2^31).

Sample

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

Ideas:

When I saw this question, the first thing that came to my mind was the Queen n question. For those who don't remember much, you can look at this article, they all continue to search for the next line if the conditions of this line are met.But this question is a bit different. The problem of n queens is that n rows and n queens must be filled, and this question is difficulty 1:n rows only need to be filledk is OK, so this is a difficult point.How to solve it?In the n queens, the condition is satisfied when the current number of rows is greater than the total n rows, then we are actually similar here. We need to create a new parameter m here, which represents the number of chess pieces we have placed, when the number of chess pieces is equal to the target k valueTime is a plan.Difficulty 2:Two pieces cannot be placed on the same row or column on the board.In fact, the same line is easy to handle, because we will not repeat it at all, because when there is a column in the current line that satisfies the condition, we directly search for the next line, so there will be no conflict.What about the same column?In fact, it is also simple, that is, we directly define an array to indicate whether the current column has been selected, because the same column, of course, the same column of all rows is represented by the same pos[j].

Code:

#include#include#include#include#include#include#include#includeusing namespace std;char c[10][10];int cnt;//Number of programsint n,k,m;//n is the dimension, k is the number of target pieces, m is the number of pieces currently placedint pos[10];//Mark the selection of each column, if it is selected, it will be 1int vis[10][10];//Mark each chessboard positionvoid dfs(int t,int m){ //t is the number of rowsif(m>=k){cnt++;return;}if(t>n)return;for(int i=1;i<=n;i++){//column, which is the current row t, traverse each column under row tif(pos[i]||vis[t][i]||c[t][i]!='#')continue;//Continue if the condition is not metpos[i]=1;//This column is traversed and it is 1vis[t][i]=1;dfs(t+1,m+1);//Search for the next line if the conditions are metpos[i]=0;vis[t][i]=0;}dfs(t+1,m);//If the current line does not meet the conditions, continue to search for the next line, which is sometimes easy to ignore}int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);//These two lines are to use cin, when the cout stream clears the cache, the read and write speed is fasterwhile(cin>>n>>k){memset(c,0,sizeof(c));memset(vis,0,sizeof(vis));//Both lines are initializationif(n==-1&&k==-1)break;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>c[i][j];}}cnt=0,m=0;dfs(1,0);//The first line starts to callcout<

原网站

版权声明
本文为[_rosy]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/211/202207300435094833.html

边栏推荐

猜你喜欢

随机推荐