【冬令营 Winter Camp】搜索专题
【冬令营 Winter Camp】搜索专题
A - 棋盘问题
JavaC++
B - Perket
JavaC++
C - 全排列
JavaC++
D - 自然数拆分
JavaC++
E - Prime Ring Problem
JavaC++
F - Red and Black
JavaC++
G - Knight Moves
JavaC++
H - Oil Deposits
C++
I - Lake Counting
JavaC++
J - 二叉树先序遍历
JavaC++
K - 迷宫(一)
Java
L - 马走日
JavaC++
M - 八皇后问题
JavaC++
N - 选数
JavaC++
O - 打开灯泡 Switch the Lamp On
C++
总结
A - 棋盘问题
在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。
Sample Input
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
2
1
思路:深度优先遍历,一行一行判断能否放棋子,每一行需要判断每一列能否放能放,能放/不能放也都递归到下一行(这样能包含所有放棋子的情况),注意回溯。
Java
import java.util.Scanner;
public class Main {
static int n, k, cnt;
static char[][] array;
static boolean[] used;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
n = sc.nextInt();
k = sc.nextInt();
if (n == -1 && k == -1)
break;
cnt = 0;
array = new char[n][n];
used = new boolean[n];
sc.nextLine();
for (int i = 0; i < n; i++) {
array[i] = sc.nextLine().toCharArray();
}
dfs(0, 0);
System.out.println(cnt);
}
}
public static void dfs(int i, int sum) {
if (i == n) {
if (sum == k) {
cnt++;
}
return;
}
for (int j = 0; j < n; j++) {
if (array[i][j] == '.')
continue;
if (!used[j]) {
used[j] = true;
dfs(i+1, sum+1);
used[j] = false;
}
}
dfs(i+1, sum);
}
}
C++
#include
#include
using namespace std;
int n, k, cnt;
char a[10][10];
bool flag[10];
void dfs(int x, int sum) {
if (x == n) {
if (sum == k)
cnt++;
return;
}
// 遍历一行的每一列,判断能否放棋子
for (int i = 0; i < n; i++) {
if (a[x][i] == '.' || flag[i]) // 如果当前x,i位置为.或者是所在行列已经被占用则跳过
continue;
flag[i] = true; // 修改标记数组
dfs(x+1, sum+1); // 放一枚棋子递归下一行
flag[i] = false; // 回溯
}
// 这一行不放棋子,跳过(模拟所有)
dfs(x+1, sum);
}
int main() {
while (1) {
cin >> n >> k;
if (n == -1 && k == -1)
break;
// 每次测试都需要修改全局变量的初始值
memset(flag, false, sizeof(flag));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
}
}
cnt = 0;
dfs(0, 0);
printf("%dn", cnt);
}
return 0;
}
B - Perket
你有 N 种配料,每种配料有酸度 S 和苦度 B 。用这些配料做成Perket时,总的酸度为所有配料酸度的乘积,总的苦度是所有配料苦度的和。你至少需要添加一种配料。
为了使口感适中,总的酸度和苦度之差的绝对值应该尽可能小,求这个最小值。
4
1 7
2 6
3 8
4 9
1
Java
import java.util.Scanner;
public class Main {
static int n, k, cnt;
static int[][] array;
static boolean[] used;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
array = new int[n][2];
cnt = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
array[i][0] = sc.nextInt();
array[i][1] = sc.nextInt();
}
dfs(0, 1, 0, 0);
System.out.println(cnt);
}
public static void dfs(int i, int a, int b, int k) {
if (i == n) {
if (k > 0)
cnt = Math.min(cnt, Math.abs(a - b));
return;
}
dfs(i+1, a*array[i][0], b + array[i][1], k+1);
dfs(i+1, a, b, k);
}
}
C++
#include
using namespace std;
typedef long long ll;
const ll N = 1E5 + 7;
ll current_exception = 1e9+10;
ll arr[10][2];
ll n, k, cnt = 1e9+1;
void dfs(ll i, ll a, ll b) {
if (i == n) {
if (k > 0)
cnt = min(cnt, abs(a - b));
return;
}
k++;
dfs (i + 1, a * arr[i][0], b + arr[i][1]);
k--;
dfs(i + 1, a, b);
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i][0] >> arr[i][1];
}
dfs(0, 1, 0);
cout << cnt;
}
思路:n<=10,数据较小,暴力求解,每一个都试试加入和不加入两种情况,取最小值,来源:大佬博客
#include
#include
#include
#include
#include
评论列表(0条)