Code – 第234页

蓝桥杯 BASIC-27 基础练习 2n皇后问题

问题描述
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
输入格式
输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
输出格式
输出一个整数，表示总共有多少种放法。
样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
2
样例输入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
0

分析：和n皇后问题一样，只不过2n皇后要用两个深度优先搜索。
调用放置白皇后的递归dfs，先放置白皇后，当每一个白皇后放置成功之后，在递归的return语句之前，
新建一个棋盘，复制原来的棋盘后并把放置了白皇后的位置置为0，调用摆放黑皇后的深度优先搜索。
当黑皇后也找到相应的解法后，cnt++; 最后输出cnt的值。

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int cnt = 0;

bool issafe(vector<vector<int> > pic, vector<int> pos, int row) {
    for(int i = 0; i < row; i++) {
        if(pos[i] == pos[row] || abs(i - row) == abs(pos[i] - pos[row]))
            return false;
    }
    return true;
}

void blackdfs(vector<vector<int> > blackpic, vector<int> blackpos, int n, int blackrow) {
    if(blackrow == n) {
        cnt++;
        return ;
    }
    for(blackpos[blackrow] = 0; blackpos[blackrow] < n; blackpos[blackrow]++) {
        if(blackpic[blackrow][blackpos[blackrow]] == 1 && issafe(blackpic, blackpos, blackrow)) {
            blackdfs(blackpic, blackpos, n, blackrow + 1);
        }
    }
}


void dfs(vector<vector<int> > pic, vector<int> pos, int n, int row) {
    if(row == n) {
        vector<vector<int> > blackpic(n, vector<int>(n));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                blackpic[i][j] = pic[i][j];
            }
        }
        for(int i = 0; i < n; i++) {
            blackpic[i][pos[i]] = 0;
        }
        vector<int> blackpos(n);
        blackdfs(blackpic, blackpos, n, 0);
        return ;
    }
    for(pos[row] = 0; pos[row] < n; pos[row]++) {
        if(pic[row][pos[row]] == 1 && issafe(pic, pos, row)) {
            dfs(pic, pos, n, row + 1);
        }
    }
}

int main() {
    int n;
    cin >> n;
    vector<vector<int> > pic(n, vector<int>(n));
    vector<int> pos(n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> pic[i][j];
        }
    }
    dfs(pic, pos, n, 0);
    cout << cnt;
    return 0;
}

#include <iostream>

#include <cmath>

#include <vector>

using namespace std;

int cnt = 0;

bool issafe(vector<vector<int> > pic, vector<int> pos, int row) {

for(int i = 0; i < row; i++) {

if(pos[i] == pos[row] || abs(i - row) == abs(pos[i] - pos[row]))

return false;

}

return true;

}

void blackdfs(vector<vector<int> > blackpic, vector<int> blackpos, int n, int blackrow) {

if(blackrow == n) {

cnt++;

return ;

}

for(blackpos[blackrow] = 0; blackpos[blackrow] < n; blackpos[blackrow]++) {

if(blackpic[blackrow][blackpos[blackrow]] == 1 && issafe(blackpic, blackpos, blackrow)) {

blackdfs(blackpic, blackpos, n, blackrow + 1);

}

void dfs(vector<vector<int> > pic, vector<int> pos, int n, int row) {

if(row == n) {

vector<vector<int> > blackpic(n, vector<int>(n));

for(int i = 0; i < n; i++) {

for(int j = 0; j < n; j++) {

blackpic[i][j] = pic[i][j];

}

for(int i = 0; i < n; i++) {

blackpic[i][pos[i]] = 0;

}

vector<int> blackpos(n);

blackdfs(blackpic, blackpos, n, 0);

return ;

}

for(pos[row] = 0; pos[row] < n; pos[row]++) {

if(pic[row][pos[row]] == 1 && issafe(pic, pos, row)) {

dfs(pic, pos, n, row + 1);

}

int main() {

int n;

cin >> n;

vector<vector<int> > pic(n, vector<int>(n));

vector<int> pos(n);

for(int i = 0; i < n; i++) {

for(int j = 0; j < n; j++) {

cin >> pic[i][j];

}

dfs(pic, pos, n, 0);

cout << cnt;

return 0;

}

蓝桥杯 ADV-203 算法提高 8皇后·改(八皇后问题)

问题描述
规则同8皇后问题，但是棋盘上每格都有一个数字，要求八皇后所在格子数字之和最大。
输入格式
一个8*8的棋盘。
输出格式
所能得到的最大数字和
样例输入
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
样例输出
260
数据规模和约定
棋盘上的数字范围0~99

#include <iostream>
#include <cmath>
using namespace std;
int maxvalue = 0;
int pic[8][8];

bool issafe(int pos[], int row) {
    for(int i = 0; i < row; i++) {
        if(pos[i] == pos[row] || abs(i - row) == abs(pos[i] - pos[row]))
            return false;
    }
    return true;
}
void dfs(int pos[], int row) {
    if(row == 8) {
        int sum = 0;
        for(int i = 0; i < 8; i++) {
            sum += pic[i][pos[i]];
        }
        maxvalue = sum > maxvalue ? sum : maxvalue;
        return ;
    }
    for(pos[row] = 0; pos[row] < 8; pos[row]++) {
        if(issafe(pos, row)) {
            dfs(pos, row + 1);
        }
    }
}

int main() {
    int pos[8];
    for(int i = 0; i < 8; i++) {
        for(int j = 0; j < 8; j++) {
            cin >> pic[i][j];
        }
    }
    dfs(pos, 0);
    cout << maxvalue;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int maxvalue = 0;

int pic[8][8];

bool issafe(int pos[], int row) {

for(int i = 0; i < row; i++) {

if(pos[i] == pos[row] || abs(i - row) == abs(pos[i] - pos[row]))

return false;

}

return true;

}

void dfs(int pos[], int row) {

if(row == 8) {

int sum = 0;

for(int i = 0; i < 8; i++) {

sum += pic[i][pos[i]];

}

maxvalue = sum > maxvalue ? sum : maxvalue;

return ;

}

for(pos[row] = 0; pos[row] < 8; pos[row]++) {

if(issafe(pos, row)) {

dfs(pos, row + 1);

}

int main() {

int pos[8];

for(int i = 0; i < 8; i++) {

for(int j = 0; j < 8; j++) {

cin >> pic[i][j];

}

dfs(pos, 0);

cout << maxvalue;

return 0;

}

LeetCode 52. N-Queens II

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

分析：和LeetCode 51. N-Queens一样，只需改动几行代码即可~

class Solution {
    int cnt = 0;
public:
    int totalNQueens(int n) {
        vector<int> pos(n);
        dfs(pos, n, 0);
        return cnt;
    }
private:
    void dfs(vector<int> &pos, int n, int row) {
        if(row == n) {
            cnt++;
            return ;
        }
        for(pos[row] = 0; pos[row] < n; pos[row]++) {
            if(issafe(pos, n, row)) {
                dfs(pos, n, row + 1);
            }
        }
    }
    
    bool issafe(vector<int> &pos, int n, int row) {
        for(int i = 0; i < row; i++)
            if(pos[i] == pos[row] || abs(i - row) == abs(pos[i] - pos[row]))
                return false;
        return true;
    }
};

class Solution {

int cnt = 0;

public:

int totalNQueens(int n) {

vector<int> pos(n);

dfs(pos, n, 0);

return cnt;

}

private:

void dfs(vector<int> &pos, int n, int row) {

if(row == n) {

cnt++;

return ;

}

for(pos[row] = 0; pos[row] < n; pos[row]++) {

if(issafe(pos, n, row)) {

dfs(pos, n, row + 1);

}

bool issafe(vector<int> &pos, int n, int row) {

for(int i = 0; i < row; i++)

if(pos[i] == pos[row] || abs(i - row) == abs(pos[i] - pos[row]))

return false;

return true;

}

};

LeetCode 51. N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[
[“.Q..”, // Solution 1
“…Q”,
“Q…”,
“..Q.”],

[“..Q.”, // Solution 2
“Q…”,
“…Q”,
“.Q..”]
]

分析：pos[i]存放的是第i行的皇后所在的位置，递归以行的形式递归，每次放置的皇后要判断是否与前面已经放置的皇后冲突。从pos[row] = 0开始一直到n-1，判断是否安全如果安全就进行下一行的摆放，每次递归到row==n的时候表示当前所有n个皇后已经摆放完成，此时将当前完成的结果保存在string类型的temp数组里面，先将数组置为’…..’，后根据pos[i]存放i行皇后的位置的特性将temp数组里面temp[i][pos[i]]置为’Q’。然后将temp压入v数组中，return。这样递归结束就能找到所有的摆放方法。这是一个深度优先的过程，从在第一行放在第一个位置开始，摆放第二行、第三行…直到最后一行。然后pos[row]++,表示将第一行放在第二个位置…然后摆放第二行、第三行…直到最后一行……直到所有的情况深度优先搜索完成～

class Solution {
    vector<vector<string> > v;
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<int> pos(n);
        dfs(pos, n, 0);
        return v;
    }
private:
    void dfs(vector<int> &pos, int n, int row) {
        if(row == n) {
            vector<string> temp(n, string(n, '.'));
            for(int i = 0; i < n; i++) {
                temp[i][pos[i]] = 'Q';
            }
            v.push_back(temp);
            return ;
        }
        for(pos[row] = 0; pos[row] < n; pos[row]++) {
            if(issafe(pos, n, row)) {
                dfs(pos, n, row + 1);
            }
        }
    }
    
    bool issafe(vector<int> &pos, int n, int row) {
        for(int i = 0; i < row; i++)
            if(pos[i] == pos[row] || abs(i - row) == abs(pos[i] - pos[row]))
                return false;
        return true;
    }
};

class Solution {

vector<vector<string> > v;

public:

vector<vector<string>> solveNQueens(int n) {

vector<int> pos(n);

dfs(pos, n, 0);

return v;

}

private:

void dfs(vector<int> &pos, int n, int row) {

if(row == n) {

vector<string> temp(n, string(n, '.'));

for(int i = 0; i < n; i++) {

temp[i][pos[i]] = 'Q';

}

v.push_back(temp);

return ;

}

for(pos[row] = 0; pos[row] < n; pos[row]++) {

if(issafe(pos, n, row)) {

dfs(pos, n, row + 1);

}

bool issafe(vector<int> &pos, int n, int row) {

for(int i = 0; i < row; i++)

if(pos[i] == pos[row] || abs(i - row) == abs(pos[i] - pos[row]))

return false;

return true;

}

};

蓝桥杯 BASIC-19 基础练习完美的代价

问题描述
回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
交换的定义是：交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文！完美！)
输入格式
第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)
第二行是一个字符串，长度为N.只包含小写字母
输出格式
如果可能，输出最少的交换次数。
否则输出Impossible
样例输入
5
mamad
样例输出
3
分析：过程见代码注释部分。其中有两个注意点：
1.impossible的情况：如果有一个字符出现的次数是奇数次数，而且n是偶数，那么不可能构成回文
如果n是奇数，但是已经有一个字符出现的次数是奇数次数了，那么如果又有一个字符是奇数次数，就不可能构成回文。
2.如果n是奇数，计算中间那个字符交换的次数的时候，不需要模拟把这个数移动到中间去，因为移动到中间的话假设有一对数都在左边或者都在右边，
那么交换成回文的时候就要经过中间，就会每次把cnt多加了1，而这个1是没有必要的，因为可以所有的回文移动完了之后再把这个独立的奇数移动过去，才能保证交换次数最少。

#include <iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	int j = n - 1;
	int cnt = 0;//cnt用来统计交换的次数
	int flag = 0;//flag判断是否已经有一个单独的奇个数的字符了
	for(int i = 0; i < j; i++) {//i指针从头遍历到倒数第二个字符
		for(int k = j; k >= i; k--) {//k指针从后面往前一直到i寻找和s[i]相同的s[k]
			if(k == i) {//如果找不到相同的
				if(n % 2 == 0 || flag == 1) {//impossible的两种情况
					cout << "Impossible";
					return 0;
				}
				flag = 1;
				cnt += n / 2 - i;
			} else if(s[k] == s[i]) {
				for(int l = k; l < j; l++) {
					swap(s[l], s[l+1]);//把s[k]换到s[j]处
					cnt++;//统计交换次数
				}
				j--;
				break;
			}
		}
	}
	cout << cnt;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

string s;

cin >> s;

int j = n - 1;

int cnt = 0;//cnt用来统计交换的次数

int flag = 0;//flag判断是否已经有一个单独的奇个数的字符了

for(int i = 0; i < j; i++) {//i指针从头遍历到倒数第二个字符

for(int k = j; k >= i; k--) {//k指针从后面往前一直到i寻找和s[i]相同的s[k]

if(k == i) {//如果找不到相同的

if(n % 2 == 0 || flag == 1) {//impossible的两种情况

cout << "Impossible";

return 0;

}

flag = 1;

cnt += n / 2 - i;

} else if(s[k] == s[i]) {

for(int l = k; l < j; l++) {

swap(s[l], s[l+1]);//把s[k]换到s[j]处

cnt++;//统计交换次数

}

j--;

break;

}

cout << cnt;

return 0;

}

蓝桥杯 ALGO-126 算法训练水仙花

问题描述
判断给定的三位数是否水仙花数。所谓水仙花数是指其值等于它本身每位数字立方和的数。例 153 就是一个水仙花数。 153=13+53+33
输入格式
一个整数。
输出格式
是水仙花数,输出”YES”,否则输出”NO”(不包括引号)
样例输入
123
样例输出
NO
数据规模和约定
一个三位的整数,否则输出”NO”

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    cin >> s;
    int a = 0;
    int sum = 0;
    for(int i = 0; i < s.length(); i++) {
        int temp = s[i] - '0';
        a = a * 10 + temp;
        sum += (temp * temp * temp);
    }
    if(sum == a) {
        cout << "YES";
    } else {
        cout << "NO";
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

cin >> s;

int a = 0;

int sum = 0;

for(int i = 0; i < s.length(); i++) {

int temp = s[i] - '0';

a = a * 10 + temp;

sum += (temp * temp * temp);

}

if(sum == a) {

cout << "YES";

} else {

cout << "NO";

}

return 0;

}