算法 搜索DFSBFS

[TOC]

二分

leetcode 392. 判断子序列

问题描述

给定字符串 st ,判断 s 是否为 t 的子序列。

你可以认为 st 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。

字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace""abcde"的一个子序列,而"aec"不是)。

示例 1:
s = "abc", t = "ahbgdc"

返回 true.

示例 2:
s = "axc", t = "ahbgdc"

返回 false.

思路二分法

  1. 用哈希集合hase_set记录下t中每个字符出现过的位置,即最多有26个key
  2. 对s中每个字母进行匹配,s[i]一定出现在s[i-1]之后,所以匹配s[i]的时候,应该找hash_set[s[i]]中大于s[i-1]的索引的索引值
  3. 我们用匹配左边界的二分法(即匹配第一个大于等于目标值的数),找当前字母索引列表中第一个大于上一个字母索引的值
  4. 如果某个匹配到的边界值等于当前字幕索引列表的长度,则表明无法匹配当前字母,返回False
  5. 全部成功匹配返回True
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
boolean isSubsequence(String s, String t) {
int m = s.length(), n = t.length();
// 对 t 进行预处理
ArrayList<Integer>[] index = new ArrayList[256];
for (int i = 0; i < n; i++) {
char c = t.charAt(i);
if (index[c] == null)
index[c] = new ArrayList<>();
index[c].add(i);
}

// 串 t 上的指针
int j = 0;
// 借助 index 查找 s[i]
for (int i = 0; i < m; i++) {
char c = s.charAt(i);
// 整个 t 压根儿没有字符 c
if (index[c] == null) return false;
int pos = left_bound(index[c], j);
// 二分搜索区间中没有找到字符 c
if (pos == index[c].size()) return false;
// 向前移动指针 j
j = index[c].get(pos) + 1;
}
return true;
}

BFS

BFS模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void BFS(){
初始化队列Q;
起点S入队;
标记S已经访问;
while(Q非空){
取Q的队首元素U;
U出队列;
if(u==目标状态){
返回结果;
}
for(所有与U相邻的元素){
if(相邻的元素合法 && 未访问){
入队;
标记访问;
}
}
}
}

填涂颜色

题目描述

由数字00组成的方阵中,有一任意形状闭合圈,闭合圈由数字11构成,围圈时只走上下左右44个方向。现要求把闭合圈内的所有空间都填写成22.例如:6 \times 66×6的方阵(n=6n=6),涂色前和涂色后的方阵如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入:
6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
输出:
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
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
49
import java.util.LinkedList;
import java.util.Scanner;

public class 填涂颜色 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] direct = { { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 0 } };//方向下、左、上、右!!!顺序关系具体得看题目要求!
int[][] map = new int[n + 2][n + 2];// 题目所需地图
int[][] visited = new int[n + 2][n + 2];// 标记是否被访问过
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
map[i][j] = sc.nextInt();
}
}
sc.close();
LinkedList<Integer> x = new LinkedList<>();//存储x的坐标
LinkedList<Integer> y = new LinkedList<>();//存储y的坐标
//需要先将(0,0)位置加入到队列中,并把该位置标为已访问
x.addLast(0);
y.addLast(0);
visited[0][0] = 1;
while (x.size() != 0) {
//遍历四个方向
for (int i = 0; i < direct.length; i++) {
int dx = x.getFirst() + direct[i][0];//注意此时仅为取出,而不能是去掉
int dy = y.getFirst() + direct[i][1];
if (dx >= 0 && dx <= n + 1 && dy >= 0 && dy <= n + 1 && visited[dx][dy] == 0 && map[dx][dy] == 0) {//判断是否越界、被访问过、以及题目要求的为0
x.addLast(dx);
y.addLast(dy);
visited[dx][dy]=1;
}
}
x.removeFirst();//当四个方向都遍历完成后才能去掉
y.removeFirst();
}
//输出结果
for (int i = 1; i <=n; i++) {
for (int j = 1; j <=n; j++) {
if(map[i][j]==0&&visited[i][j]==0)
System.out.print(2+" ");
else
System.out.print(map[i][j]+" ");
}
System.out.println();
}

}
}

马的遍历

题目描述

有一个n*m的棋盘(1<n,m<=400),在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步

输入格式

一行四个数据,棋盘的大小和马的坐标

输出格式

一个n*m的矩阵,代表马到达某个点最少要走几步(左对齐,宽5格,不能到达则输出-1)

输入

1
3 3 1 1

输出

1
2
3
0    3    2    
3 -1 1
2 1 4
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
49
50
51
52
package luogu;

import java.util.LinkedList;
import java.util.Scanner;

class Node{//也可以不用结构体做,参考奇怪的电梯
int x,y,step;
Node(int x,int y,int step){
this.x=x;
this.y=y;
this.step=step;
}
}
public class 马的遍历 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int desX = sc.nextInt() - 1;
int desY = sc.nextInt() - 1;
sc.close();
int[][] map = new int[n][m];
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
map[i][j] = -1;
}
}
int[][] dir = { { 2, -1 }, { 1, -2 }, { -1, -2 }, { -2, -1 }, { -2, 1 }, { -1, 2 }, { 1, 2 }, { 2, 1 } };
LinkedList<Node> Q = new LinkedList<>();
Q.addLast(new Node(desX,desY,0));
map[desX][desY] = 0;
while (Q.size() != 0) {

for (int i = 0; i < dir.length; i++) {
int dx = Q.getFirst().x + dir[i][0];
int dy = Q.getFirst().y + dir[i][1];
if (dx >= 0 && dx < n && dy >= 0 && dy < m && map[dx][dy] == -1) {
Q.addLast(new Node(dx,dy,Q.getFirst().step+1));
map[dx][dy]=Q.getFirst().step+1;
}
}
Q.removeFirst();
}
for (int[] t1 : map) {
for (int t2 : t1) {
System.out.print(t2 + " ");
}
System.out.println();
}

}
}

奇怪的电梯

题目描述

呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第i层楼 (1≤i≤N) 上有一个数字Ki (0≤Ki≤N)。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如:3, 3 ,1 ,2 ,53,3,1,2,5代表了Ki(K1=3,K2=3,…)Ki(K1=3,K2=3,…),从11楼开始。在11楼,按“上”可以到44楼,按“下”是不起作用的,因为没有-2−2楼。那么,从AA楼到BB楼至少要按几次按钮呢?

输入格式

共二行。

第一行为3个用空格隔开的正整数,表示N,A,B(1≤N≤200, 1≤A,B≤N)。

第二行为N个用空格隔开的非负整数,表示Ki。

输出格式

一行,即最少按键次数,若无法到达,则输出−1。

输入

1
2
5 1 5
3 3 1 2 5

输出

1
3
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
package luogu;

import java.util.LinkedList;
import java.util.Scanner;

public class 奇怪的电梯{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a = sc.nextInt();
int b = sc.nextInt();
int[] e = new int[n+1];
for (int i = 1; i <=n; i++) {
e[i] = sc.nextInt();
}
sc.close();
int[] vis = new int[n+1];
LinkedList<Integer> queue = new LinkedList<>();
LinkedList<Integer> step = new LinkedList<>();
queue.addLast(a);
step.addLast(0);
vis[a]=1;
while(queue.size()!=0){
if(queue.getFirst()==b){
System.out.println(step.getFirst());
return;
}
int t = queue.getFirst()+e[queue.getFirst()];
if(t<=n&&vis[t]==0){
queue.addLast(t);
step.addLast(step.getFirst()+1);
vis[t]=1;
}
t = queue.getFirst()-e[queue.getFirst()];
if(t>0&&vis[t]==0){
queue.addLast(t);
step.addLast(step.getFirst()+1);
vis[t]=1;
}
queue.removeFirst();
step.removeFirst();
}
System.out.println(-1);
}
}

01迷宫

题目描述

有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上,那么你可以移动到相邻4格中的某一格1上,同样若你位于一格1上,那么你可以移动到相邻4格中的某一格0上。

你的任务是:对于给定的迷宫,询问从某一格开始能移动到多少个格子(包含自身)。

输入格式

第1行为两个正整数n,m。

下面n行,每行n个字符,字符只可能是0或者1,字符之间没有空格。

接下来m行,每行22个用空格分隔的正整数i,j,对应了迷宫中第i行第j列的一个格子,询问从这一格开始能移动到多少格。

输出格式

m行,对于每个询问输出相应答案。

输入输出样例

输入 #1

1
2
3
4
5
2 2
01
10
1 1
2 2

输出 #1

1
2
4
4

说明/提示

所有格子互相可达。

对于20%20%的数据,n≤10n≤10;

对于40%40%的数据,n≤50n≤50;

对于50%50%的数据,m≤5m≤5;

对于60%60%的数据,n≤100,m≤100n≤100,m≤100;

对于100%100%的数据,n≤1000,m≤100000n≤1000,m≤100000。

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
49
50
51
52
53
54
55
56
57
58
59
60
package luogu;

import java.util.LinkedList;
import java.util.Scanner;

public class _01迷宫{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] map = new int[n+1][n+1];
int[] ans = new int[(n+1)*(n+1)];//ans数组要开大一点,刚开始开ans[1001]错了3个点
for (int i = 1; i <=n; i++) {
String c = sc.next();
char[] s = c.toCharArray();
for (int j =0; j < s.length; j++) {
map[i][j+1] = s[j]-'0';
}
}
//visited数组保存各个点所在的连通图,以及是否已经处理过,ans数组保存各个连通图的大小
int[][] visited = new int[n+1][n+1];
int[][] dir = {{1,0},{0,-1},{-1,0},{0,1}};
int color=0;//用来保存当前是在第几个连通图中
LinkedList<Integer> x = new LinkedList<>();
LinkedList<Integer> y = new LinkedList<>();
for (int i = 1; i <=n; i++) {
for (int j = 1; j <=n; j++) {
if(visited[i][j]==0){//如果当前位置不在已知连通图中(还未处理过)
color++;//记录当前所在连通图数
x.addLast(i);
y.addLast(j);
visited[i][j]=1;
int sum=1;//初始化
while(x.size()!=0){
for (int j2 = 0; j2 < dir.length; j2++) {
int dx = x.getFirst()+dir[j2][0];
int dy = y.getFirst()+dir[j2][1];
if(dx>0&&dx<=n&&dy>0&&dy<=n&&visited[dx][dy]==0&&map[x.getFirst()][y.getFirst()]!=map[dx][dy]){
x.addLast(dx);
y.addLast(dy);
// visited[dx][dy]=1;
visited[dx][dy]=color;//标记新位置在第d个连通图中
sum++;//计数器累加
}
}
x.removeFirst();
y.removeFirst();
ans[color]=sum;//保存当前连通图能移动到多少格
//ans[1]=10 颜色1有10个联通格
}
}
}
}
for (int i = 0; i < m; i++) {
int sx = sc.nextInt();
int sy = sc.nextInt();
System.out.println(ans[visited[sx][sy]]);//直接查找答案并输出
}
}
}

蓝桥杯迷宫

要求按字典序 打印轨迹

运行结果

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
public class Main {
//注意dir于d的对应关系
//向下则行数加一,列数不变!!!!!
static int[][] dir = { { 1, 0 }, { 0, -1 }, { 0, 1 }, { -1, 0 } };
static char[] d = { 'D', 'L', 'R', 'U' };//题目要求字典序
static int[][] map = {
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0,
0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1 },
{ 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0,
0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0,
1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1 },
{ 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0,
0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1,
1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0,
0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1,
1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0 },
{ 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0,
0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 },
{ 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0,
0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1 },
{ 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1,
0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0,
0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1,
1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0,
0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1 },
{ 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0,
1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0,
0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1 },
{ 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0,
1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1 },
{ 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0,
0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0,
1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1 },
{ 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1,
0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1 },
{ 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1,
0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0,
0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 },
{ 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0,
1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1,
1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1 },
{ 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0,
1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0,
1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1 },
{ 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1,
1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0 }

};
static boolean[][] vis = new boolean[35][55];

public static void main(String[] args) {
bfs(1, 1, 0, "");//从1,1开始(注意下标从零开始)
}

public static void bfs(int x, int y, int num, String s) {
LinkedList<Node> q = new LinkedList<Node>();//创建队列
q.addFirst(new Node(x, y, num, s));//加入该点
vis[x][y] = true;//标记为真
while (q.size() != 0) {
Node tmp = q.getFirst();
q.removeFirst();
if (tmp.x == 30 && tmp.y == 50) {//到终点了,由于是队列,所以是最小步数
System.out.println(tmp.step);//打印步数
System.out.println(tmp.s);//打印轨迹
return;//找到了就可以直接return了
}
for (int i = 0; i < dir.length; i++) {
int dx = tmp.x + dir[i][0];
int dy = tmp.y + dir[i][1];
if (dx > 0 && dx <= 30 && dy > 0 && dy <= 50 && !vis[dx][dy] && map[dx][dy] == 0) {
vis[dx][dy] = true;
q.addLast(new Node(dx, dy, tmp.step + 1, tmp.s + d[i]));
}
}
}
}
}

class Node {
int x;//x坐标
int y;//y坐标
int step;//步数
String s;//轨迹
Node(int x, int y, int step, String s) {
this.step = step;
this.x = x;
this.y = y;
this.s = s;
}
}

字串变换

题目描述

已知有两个字串A,BA,B及一组字串变换的规则(至多6个规则):

A1 ->B1

A2 -> B2

规则的含义为:在 AA中的子串 A1 可以变换为B_1B1,A_2A2 可以变换为 B2 …。

例如:A=abcd,B=xyz

变换规则为:

abcxuudyyyz

则此时,AA可以经过一系列的变换变为BB,其变换的过程为:

abcdxudxyxyz

共进行了33次变换,使得AA变换为BB。

输入格式

输入格式如下:

AA BB
A1 B1
A2 B2 |-> 变换规则

… … /

所有字符串长度的上限为2020。

输出格式

输出至屏幕。格式如下:

若在1010步(包含1010步)以内能将AA变换为BB,则输出最少的变换步数;否则输出”NO ANSWER!”

输入

1
2
3
4
abcd xyz
abc xu
ud y
y yz

输出

1
3
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>     //万能头文件
using namespace std;
string a,b; //字符串A与字符串B
string sa[8],sb[8]; //存放6种转换方式
map<string,int> map1; //用map存放已经宽搜过的字符串,用来判重剪枝(否则会超时)
int l; //有l种转换方式
queue<string> q; //存放转换出来的字符串
queue<int> bb; //存放当前转换出来的字符串已经使用的步数
int bfs()
{
int i,j,k,m,n;
string s,ss;
while (q.empty()==0&&q.front()!=b&&bb.front()<=10) //当还能继续转换且没转换出字符串B且步数也没有超出10步时进行宽搜
{
if (map1[q.front()]==1) //剪枝:如果当前字符串已经宽搜过了,就弹出,进入下一次循环.
{
q.pop();
bb.pop();
continue;
}
map1[q.front()]=1; //记录下该字符串
for (i=1;i<=l;i++) //循环出每一种转换方式
{
s=q.front(); //将S赋值为当前要操作的字符串
while (1) //找出子串sa[i]的所有位置
{
m=s.find(sa[i]); //在S里查找子串sa[i]的第一次出现位置
if (m==-1) break; //如果全找出来(找不到)了,就结束循环
ss=q.front(); //将SS赋值为当前要操作的字符串
ss.replace(m,sa[i].size(),sb[i]); //在SS中用子串sb[i]替换掉S里第一次出现的子串sa[i]
q.push(ss); //将转换后的SS压入队列
bb.push(bb.front()+1); //将转换后的SS已经使用的步数压入队列
s[m]='~'; //将S里子串sa[i]的第一次出现位置随便换成另一种无关的字符,这样就可以查找到S里子串sa[i]的下一个出现位置
}

}
q.pop(); //将操作过的字符串弹出队列
bb.pop(); //操作过的字符串已经用过的步数一块弹出
}
if (q.empty()==1||bb.front()>10) return -1;//没法再进行宽搜,或者超出步数,就返回-1
else return bb.front(); //否则,就是找到了,便返回最少使用步数
}
int main()
{
int i,j,k,m,n;
cin>>a>>b; //读入字符串A与字符串B
l=1;
while (cin>>sa[l]>>sb[l]) l++; //读入转换方式
l--; //l初始值为1,所以要减1,才能表示转换方式的数量
if (l==0&&a!=b) //若果没有转换方式且A也不等于B,直接输出"NO ANSWER!"(其实这步可以不要)
{
cout<<"NO ANSWER!";
return 0;
}
q.push(a); //将字符串A压入队列
bb.push(0); //将初始步数0压入队列
k=bfs(); //宽搜
if (k==-1) //返回-1说明NO ANSWER!
{
cout<<"NO ANSWER!";
return 0;
}
cout<<k; //输出最小步数
}

机器人搬重物

题目描述

机器人移动学会(RMI)现在正尝试用机器人搬运物品。机器人的形状是一个直径1.61.6米的球。在试验阶段,机器人被用于在一个储藏室中搬运货物。储藏室是一个 N \times MN×M 的网格,有些格子为不可移动的障碍。机器人的中心总是在格点上,当然,机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有:向前移动11步(Creep);向前移动2步(Walk);向前移动33 步(Run);向左转(Left);向右转(Right)。每个指令所需要的时间为11 秒。请你计算一下机器人完成任务所需的最少时间。

输入格式

第一行为两个正整数N,M(N,M \le 50)N,M(N,M≤50),下面NN行是储藏室的构造,00表示无障碍,11表示有障碍,数字之间用一个空格隔开。接着一行有44个整数和11个大写字母,分别为起始点和目标点左上角网格的行与列,起始时的面对方向(东EE,南SS,西WW,北NN),数与数,数与字母之间均用一个空格隔开。终点的面向方向是任意的。

输出格式

一个整数,表示机器人完成任务所需的最少时间。如果无法到达,输出-1−1。

img
输入

1
2
3
4
5
6
7
8
9
10
11
9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 S

输出

1
12

这道题,毫无疑问,就是广搜。但是它要注意的细节非常多。所以这道题对逻辑和代码能力的的考察很高

首先,这道题需要注意,障碍物是在格子上,而机器人是在格点上走。某人就是我自信地写完了代码后发现题读错了。关键最讨厌的是样例居然能过……

那么这道题经过信息整理可以发现,我们需要两个数组:一个存方格上障碍物的位置(sd[i][j]数组表示),一个存机器人可以走的格点的位置(a[i][j])数组表示,则根据样例我们可以整理成这张图: 样例图示 其中黑色为数组sd[i][j]的下标,绿色为a[i][j]的下标。根据题目可以发现,机器人本身也有宽度,所以边界和障碍物的四周,不能走,那么机器人可以到达的地方就是图中蓝色框内的绿色格点。所以边界条件判断时,n和m各要减1。

然后我们还需要注意的地方是题中害人不浅的方向处理。于是为了方便存储,我给每个方向都编了一个号:↑为1,↓为2,←为3,→为4。然后转向的时候就更加麻烦了。于是我为了好判断情况,emm……用了好几个数组

1
2
3
4
5
int fx[5]={0,-1,1,0,0};//fx[i]表方向i(编号)的x的进退情况  
int fy[5]={0,0,0,-1,1};//fy[i]表方向i(编号)的y的进退情况
int ft[5]={0,1,4,2,3};//ft[i]表示顺时针排列各个方向的编号(上1 右4 下2 左3)
int fft[5]={0,1,3,4,2};//fft[i]表示数字i在ft[]数组中的下标
int abc[5]={0,1,2,1,0};//abc[5]表示转到[顺时针转i次到达的那个方向]的最短次数

其中ft数组和abc数组比较难理解

先讲abc数组 abc数组解释 如图,不难看出当对于不同的i,也就是顺时针转动i次时,对应的最小旋转次数就是abc[i]

而ft数组也比较好理解 abc图中蓝圈内四个方向各有一个黑色数字代表方向编号,那么我们顺时针遍历一下就是1 4 2 3.

我么还要注意的地方是起点和终点可能重合,需要特判;起点可能就有障碍物,也要特判。

最后要注意的是,对于每一步,你走一个格点,两个格点或三个格点所耗时间都是1,不要搞乱;而每转90°,就要耗一定时间,所以千万要小心。

于是,开始写BFS

用队列存储每一个格点的信息,然后起点入队,每次从队首取出一个元素,根据这个元素旋转,直行,得到一个新的坐标,然后判断由这种方式到达的这个点是否是耗时最短的一种方式(类似于Dijkstra中的dis数组),此处用f[i][j]数组表示,然后队列为空后,输出f[终点的x][终点的y]即可。

丧心病狂的代码如下

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<iomanip>
using namespace std;
int sd[55][55];
int a[55][55];//a为读入的方格地图
int n,m;
int x11,y11;//起点
int x2,y2;//终点
int f[55][55];//f为格点地图

int fx[5]={0,-1,1,0,0};//fx[i]表方向i(编号)的x情况
int fy[5]={0,0,0,-1,1};//fy[i]表方向i(编号)的y情况
int ft[5]={0,1,4,2,3};//ft[i]表示顺时针排列各个方向的编号(上1 右4 下2 左3)
int fft[5]={0,1,3,4,2};//fft[i]表示数字i在ft[]数组中的下标

int abc[5]={0,1,2,1,0};//abc[5]表示转到[顺时针转i次到达的那个方向]的最短次数
struct node
{
int x,y;//当前点的坐标
int t;//1=>N 2=>S 3=>W 4=>E 方向编号
int time;//从起点到当前点的最短时间
};
queue<node> q;//队列q
string ch;//读入起点的方向
int cto;//起点的方向

void fxto()
{
switch(ch[0])
{
case 'N': cto=1;break;
case 'S': cto=2;break;
case 'W': cto=3;break;
case 'E': cto=4;break;
}
return;
}
void change()
{
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
if(sd[i][j]==1)//如果当前格为障碍物,则它的四个顶点都不能走
{
a[i-1][j]=1;
a[i][j-1]=1;
a[i-1][j-1]=1;
a[i][j]=1;
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
scanf("%d",&sd[i][j]);
}
}
cin>>x11>>y11>>x2>>y2;
cin>>ch;
fxto();//判断ch代表的方向
change();//把方格地图转化为机器人可以走的格点地图
node first;//起点
first.x=x11;
first.y=y11;
first.t=cto;
first.time=0;
q.push(first);//起点入队
node u,d;
while(!q.empty())
{
u=q.front();
q.pop();
for(int i=1;i<=4;++i)
{
int zhuan=abc[i];//[顺时针转i下的那个方向]的最短旋转次数

//求出旋转完了以后方向的编号fangx(为了方便讨论,全部当做顺时针旋转)
int fangx=fft[u.t]+i;//此时fangx为下标
if(fangx==5) fangx=1;
if(fangx==6) fangx=2;
if(fangx==7) fangx=3;
if(fangx==8) fangx=4;
fangx=ft[fangx];//此时fangx为方向编号
//此时fangx存的是由当前点顺时针转了i次后到达的方向的编号

for(int j=1;j<=3;++j)//走1~3步
{
int lsx=u.x+fx[fangx]*j;//计算按当前旋转方向走j步的坐标
int lsy=u.y+fy[fangx]*j;
if(lsx>=n || lsx<=0 || lsy>=m || lsy<=0 || (lsx==x11&&lsy==y11) || a[lsx][lsy]==1)
{
//判断边界和障碍物 (特判:是否为起点)
break;
}
if((u.time+zhuan+1<f[u.x+fx[fangx]*j][u.y+fy[fangx]*j] || f[u.x+fx[fangx]*j][u.y+fy[fangx]*j]==0) && a[u.x+fx[fangx]*j][u.y+fy[fangx]*j]==0)
{//如果当前点可以刷新距离,就入队
d.x=u.x+fx[fangx]*j;
d.y=u.y+fy[fangx]*j;
d.t=fangx;
d.time=u.time+zhuan+1;
f[u.x+fx[fangx]*j][u.y+fy[fangx]*j]=d.time;
q.push(d);
}
}
}
}
if(f[x2][y2]==0 && (x2!=x11 || y2!=y11))//如果为0,代表不能走到
{
cout<<"-1"<<endl;
}
else//否则输出终点的距离
cout<<f[x2][y2]<<endl;
return 0;
}

CoVH之再破难关/黑白棋

Problem

OIBH组织派出的黄金十二人+青铜五小强还没有到, 他们只能指望原先的机关能够阻拦住柯南的脚步.

柯南打开大门之后发现里面还有一个门, 门上还有一个神奇的锁(-,-)

这是一个4*4的锁, 上面有8个凸起的格子和8个被按下的格子
当且仅当两个格子有公共边时, 则称这两个格子是相邻的。

图片
每次操作只能够交换相邻的两个格子

柯南看到了初始锁的状态 和目标锁的状态
同样组织只允许他用最少步数打开锁

输入格式

第1到4行每行四个数字(1或者0),描述了初始锁状态

接着是一个空行

第6到9行每行四个数字,描述了最终锁状态

输出格式

输出文件只有一行,是一个整数n,表示最少的操作次数。


1
2
3
4
5
6
7
8
9
10
11
12
Input
1111
0000
1110
0010

1010
0101
1010
0101
Output
4
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*还有一种是bfs+map判重+状态压缩
https://www.cnblogs.com/Silence-AC/p/3234199.html
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
char a[5][5], b[5][5];
int c[9][3], d[9][3], e[9][9], v[9], w = 99999;
long long ans, q = 0;
void dfs(int t)
{
if (t == 9)//已经走了8步了
{
if (ans < w){
w = ans;
return;
}
}
if(ans>w){//剪枝
return;
}
for (int i = 1; i <= 8; i++)
{
if (v[i] == 0)
{
ans += e[t][i];
v[i] = 1;
dfs(t + 1);
//还原
v[i] = 0;
ans -= e[t][i];
}
}
}
int main()
{
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
{
cin >> a[i][j];
if (a[i][j] == '1')
{
q++;
d[q][1] = i;
d[q][2] = j;
}
}
q = 0;
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
{
cin >> b[i][j];
if (b[i][j] == '1')
{
q++;
c[q][1] = i;
c[q][2] = j;
}
}
q = 0;
for (int j = 1; j <= 8; j++){

for (int i = 1; i <= 8; i++){
e[i][j] = abs(c[i][1] - d[j][1]) + abs(c[i][2] - d[j][2]);

}
}
dfs(1);
cout << w << endl;
//while(1);
return 0;
}

油田问题(java)

问题描述
GeoSurvComp地质调查公司负责探测地下石油储藏。 GeoSurvComp现在在一块矩形区域探测石油,并把这个大区域分成了很多小块。他们通过专业设备,来分析每个小块中是否蕴藏石油。如果这些蕴藏石油的小方格相邻,那么他们被认为是同一油藏的一部分。在这块矩形区域,可能有很多油藏。你的任务是确定有多少不同的油藏。
Input
输入可能有多个矩形区域(即可能有多组测试)。每个矩形区域的起始行包含m和n,表示行和列的数量,1<=n,m<=100,如果m =0表示输入的结束,接下来是n行,每行m个字符。每个字符对应一个小方格,并且要么是’* ’,代表没有油,要么是’@’,表示有油。
Output
对于每一个矩形区域,输出油藏的数量。两个小方格是相邻的,当且仅当他们水平或者垂直或者对角线相邻(即8个方向)。
Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0

Sample Output
0
1
2
2

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
import java.util.*;

public class Main {
static int n,m;
static String[] map;//地图
static int[][] vis;//标记是否访问过
static int ans;//答案
static int[][] move = {{0,1},{0,-1},{1,0},{-1,0},{-1,-1},{1,-1},{-1,1},{1,1}};//移动方向,有时候注意题目是否要求字典序

static void dfs(int x,int y) {
for(int i = 0;i < 8;i++) {
int nx = x + move[i][0];
int ny = y + move[i][1];
if(check(nx,ny)) {
vis[nx][ny] = 1;
dfs(nx,ny);
}
}
}
static boolean check(int x,int y) {
return x >= 0 && x < n && y >= 0 && y < m && map[x].charAt(y) == '@' && vis[x][y] == 0;//保证不越界和该位为@并且未被访问过
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while(cin.hasNext()) {
n = cin.nextInt();
m = cin.nextInt();
map = new String[n];//字符型数组
vis = new int[n][m];
ans = 0;
if(n == 0 && m == 0)
break;
for(int i = 0;i < n;i++)
map[i] = cin.next();//每行输入即为一行地图
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++)
if(map[i].charAt(j) == '@' && vis[i][j] == 0) {
ans++;
vis[i][j] = 1;
dfs(i,j);
}
System.out.println(ans);
}
}
}

Whack-A-Mole

Problem

This time we’ll play a variation of Whack-A-Mole! We’ll play this game on a board with 16
holes, from which individual moles pop-up. Using a mallet you can then “whack a mole”
and make it go hide underground. As you might know, however, whacking a mole will
often have the effect of making other moles rise and come out from the ground. In this
version of the game, every time you hit a mole with the mallet you’ll cause the immediate
four adjacent holes to change: any moles currently there will hide, while new moles popup from previously empty holes.
Imagine, for example, that you find yourself in the following game configuration, and you
prepare yourself to hit the mole at position 10 with the mallet.

You will cause the moles in positons 9, 10, 11, and 14 to hide, but you’ll also make a mole
appear at position 6. Thus ending up in the next configuration.

If you then hit the mole at position 2, then all of the moles at positions 1, 2, and 6 will hide;
but a new one in position 3 will appear. There is no use of hitting empty holes, as nothing
in the board will change. You may assume that all puzzles have a solution.
Your task is to write a computer program which, given an initial board configuration, finds
ashortest sequence of moles that you can hit in order to empty the board.
There might be several correct solutions with the same optimal length, finding any of them
will be enough. Your answer should be given as a sequence of numbers with the correct
order of moles to “whack”, each separated by a single space.

Example
Find one of the shortest sequences of moles you have to hit in order to clear the board if
starting from the configuration with moles at positions 1, 2, 4, 8, 9, 10, 11, and 14.
Discussion: This is the same configuration of moles as given in the first illustration above.
After hitting moles at positions 10 and 2, you’ll end up in the following configuration.

At this point, a single hit to the mole at position 4 will clear the board.
Answer: 10 2 4
Attempts: 2 out of Infinity
Coursework uses your best attempt for grading.
Final marks: 9 / 9 (100.0%)

分析:

  1. 其实题目就是问我们怎么样敲地鼠才能使得全部地鼠都躲起来
  2. 注意有地鼠才能敲,敲完之后该位置和四周位置地鼠状态会相反(躲起来的地鼠会站起来,站起来的地鼠会躲起来)
  3. 直接记录4*4矩阵状态,然后一路BFS出结果
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import java.util.HashSet;
import java.util.LinkedList;
class matrix {
String path = "";// 存放每次所打的地鼠
boolean ma[][] = new boolean[4][4];// 局部变量,4*4的矩阵
boolean cmp(matrix b) {// 判断是否相同
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (this.ma[i][j] != b.ma[i][j])
return false;
return true;
}
}
public class Main {
//枚举四个方向
static int dir[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
/**
* 输入参数矩阵,求出结果,默认结果都能求得解,否则只需添加判断次数条件,超过则认为不能得出结果
* @param a 参数矩阵
*/
static void bfs(matrix a) {
LinkedList<matrix> q = new LinkedList<>();//实现队列效果
HashSet<matrix> st = new HashSet<>();//判断是否已经存在,存在则不再继续存储矩阵
matrix des = new matrix();//目标矩阵
q.addLast(a);//加入队列
st.add(a);//加入集合
int step = 0;//步数
while (q.size() != 0) {
int tmpSize = q.size();//每一层bfs的数量
for (int len = 0; len < tmpSize; len++) {//枚举每一层
matrix cur = q.getFirst();//从队列头取出
q.removeFirst();
if (des.cmp(cur)) {//如果找到目标矩阵,则输出
System.out.println("一共需要敲打地鼠的次数:" + step);
System.out.println("敲打地鼠的顺序为:" + cur.path);
return;
}
for (int i = 3; i >= 0; i--) {//从3开始倒序是题目要求
for (int j = 3; j >= 0; j--) {
if (cur.ma[i][j]) {//要有地鼠才能敲打
matrix tmpmatrix = new matrix();
tmpmatrix.path = cur.path + " " + (i * 4 + j + 1) + " ";//记录路径
// 克隆原先的矩阵,在进行修改时才不会影响原先矩阵
for (int k = 0; k < 4; k++) {
for (int z = 0; z < 4; z++) {
tmpmatrix.ma[k][z] = cur.ma[k][z];
}
}
tmpmatrix.ma[i][j] = !cur.ma[i][j];//敲打后地鼠下去了
for (int ll = 0; ll < 4; ll++) {//敲打周围四个方向地鼠会变化
int dx = i + dir[ll][0];
int dy = j + dir[ll][1];
if (dx >= 0 && dx < 4 && dy >= 0 && dy < 4) {
tmpmatrix.ma[dx][dy] = !cur.ma[dx][dy];//有则变无,无则变有
}
}
if (st.contains(tmpmatrix)) {//矩阵已经有,则不存,否则可能造成死循环
continue;
}
st.add(tmpmatrix);//添加到集合
q.addLast(tmpmatrix);//添加到队列
}
}
}
}
step++;
}
}
public static void main(String[] args) {
matrix now = new matrix();
// int[] test = { 7, 8, 10, 11, 14 };
// int[] test = {2,3,4,7,9,11,12,13};
// int[] test = {1,3,4,5,6,7,10,11,12,13,15,16};
// int[] test = {1,3,7,8,9,13,14,16};
int[] test = {1,2,3,4,8,10,11,12};
for (int x : test) {
if (x % 4 != 0)//可有坐标推导
now.ma[x / 4][x % 4 - 1] = true;
else //如果是最右边的一列
now.ma[x / 4 - 1][3] = true;
}
bfs(now);//bfs搜索结果
}
}

优化: 由于只用了十六个数,所以其实可以用二进制进行压缩

DFS

DFS模板

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(答案,搜索层数,其他参数){
if(层数==maxdeep){
更新答案;
return;
}
(剪枝)
for(枚举下一层可能的状态){
更新全局变量表示状态的变量;
dfs(答案+新状态增加的价值,层数+1,其他参数);
还原全局变量表示状态的变量;
}
}

选数

题目描述

  已知 n 个整数 x1,x2,…,xn,以及一个整数 k(k<n)。从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。例如当 n=4,k=3,4 个整数分别为 3,7,12,19 时,可得全部的组合与它们的和为:
3+7+12=22  3+7+19=29  7+12+19=38  3+12+19=34。
现在,要求你计算出和为素数共有多少种。
例如上例,只有一种的和为素数:3+7+19=29)。

输入描述

键盘输入,格式为:
n , k (1<=n<=20,k<n)
x1,x2,…,xn (1<=xi<=5000000)

输出描述

 屏幕输出,格式为:
一个整数(满足条件的种数)。

1
2
3
4
5
Input
4 3
3 7 12 19
Output
1
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
public class 选数 {
static int n,res,k;
static int[] a;
public static boolean isPrime(int x){
for (int i = 2; i*i <= x; i++)
if(x%i==0)
return false;
return true;
}
//p表示当前数字的下标,x表示选择了多少个数字,sum表示所加数字之和
public static void dfs(int p,int x,int sum){//注意如果p为一个值的话,还需要一个变量记录他的位置
if(x==k)//当达到k个数时不需要继续进行
if(isPrime(sum)){
res++;
return;
}

if(p>n)return;
dfs(p+1,x+1,sum+a[p]);//有选择第p个数字
dfs(p+1,x,sum);//没有选择第p个数字

}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
a = new int[n+1];
for (int i = 1; i <=n ; i++)
a[i] = sc.nextInt();
dfs(1,0,0);
System.out.println(res);
}
}

全排列问题

题目描述

输出自然数 1 到 n 所有不重复的排列,即 n 的全排列,要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数 n。1≤n≤9

输出格式

由 1∼n 组成的所有不重复的数字序列,每行一个序列。

每个数字保留 5个场宽。

输入 #1

1
3

输出 #1

1
2
3
4
5
6
1    2    3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
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
import java.util.Scanner;
public class 全排列问题{
public static int[] visited;
public static int[] used;
public static int n;
public static void pr(){
for(int i=1;i<=n;i++)
System.out.printf("%5d",used[i]);
System.out.println();
}
public static void dfs(int x){
if(x>n){
pr();
return;
}
for(int i=1;i<=n;i++){
if(visited[i]==0){
visited[i]=1;
used[x]=i;
dfs(x+1);
visited[i]=0;
}
}

}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
visited = new int[n+1];
used = new int[n+1];

dfs(1);
}
}

八皇后问题

题目描述

一个如下的 6×6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

img

上面的布局可以用序列2 4 6 1 3 5 来描述,第 i 个数字表示在第 i 行的相应位置有一个棋子,如下:

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出,解按字典顺序排列。
请输出前 3个解。最后一行是解的总个数。

输入格式

一行一个正整数 n,表示棋盘是 n×n 大小的。

输出格式

前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。

输入

1
6

输出

1
2
3
4
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
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
public class 八皇后 {
static boolean[] lie;//列
static boolean[] u;//左上到右下
static boolean[] v;//右上到坐下
static int[] a;
static int n,sum;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
lie = new boolean[n+1];
a = new int[n+1];
u = new boolean[3*n];
v = new boolean[3*n];
dfs(1);
System.out.println(sum);

}
public static void pr(){
if(sum<=3){
for (int i = 1; i <=n ; i++) {
System.out.print(a[i]+" ");
}
System.out.println();
}
}

private static void dfs(int x) {
if(x>n){
sum++;
pr();
return;
}
for (int i = 1; i <=n ; i++) {
//左上到右下u[]: 行减列为定值,加n是为了防止数组越界
//右上到左下v[]: 行加列为定值
if(!lie[i]&&!u[x-i+n]&&!v[x+i]){
lie[i]=true;
u[x-i+n]=true;
v[x+i]=true;
a[x]=i;//记录下摆放位置
dfs(x+1);//进行下一行的递归
lie[i]=false;
u[x-i+n]=false;
v[x+i]=false;
}
}
}
}

迷宫

题目背景

给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过。给定起点坐标和终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式,每次只能移动一个方格。数据保证起点上没有障碍。

输入格式

第一行N、M和T,N为行,M为列,T为障碍总数。第二行起点坐标SX,SY,终点坐标FX,FY。接下来T行,每行为障碍点的坐标。(1≤N,M≤5)

输出格式

给定起点坐标和终点坐标,问每个方格最多经过1次,从起点坐标到终点坐标的方案总数。

输入

1
2
3
2 2 1
1 1 2 2
1 2

输出

1
1
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
public class 迷宫 {
static boolean[][] visited;
static int fx,fy,n,m,res;
static int[][] dir = {{0,-1},{0,1},{-1,0},{1,0}};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
int t = sc.nextInt();
visited = new boolean[n+1][m+1];
int sx = sc.nextInt();
int sy = sc.nextInt();
fx = sc.nextInt();
fy = sc.nextInt();
for (int i = 0; i < t; i++) {
int t1 = sc.nextInt();
int t2 = sc.nextInt();
visited[t1][t2] = true;
}
visited[sx][sy]=true;
dfs(sx,sy);
System.out.println(res);
}
public static void dfs(int sx,int sy){
if(sx==fx&&sy==fy){
res++;
return;
}
for (int i = 0; i < dir.length; i++) {
int dx = sx+dir[i][0];
int dy = sy+dir[i][1];
if((dx>0&&dx<=n&&dy>0&&dy<=m)&&(!visited[dx][dy])){
visited[dx][dy]=true;
dfs(dx,dy);
visited[dx][dy]=false;
}
}
}
}

单词方阵

题目描述

给一n×n的字母方阵,内可能蕴含多个“yizhong”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 8 个方向的任一方向,同一单词摆放时不再改变方向,单词与单词之间可以交叉,因此有可能共用字母。输出时,将不是单词的字母用*代替,以突出显示单词。例如:

1
2
3
4
5
6
7
8
9
10
输入:
8 输出:
qyizhong *yizhong
gydthkjy gy******
nwidghji n*i*****
orbzsfgz o**z****
hhgrhwth h***h***
zzzzzozo z****o**
iwdfrgng i*****n*
yyyygggg y******g

输入格式

第一行输入一个数n。(7≤n≤100)。

第二行开始输入n×n的字母矩阵。

输出格式

突出显示单词的n×n矩阵。

输入

1
2
3
4
5
6
7
8
9
8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg

输出

1
2
3
4
5
6
7
8
*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g
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
49
50
51
52
/*这道题是一个DFS的题目,从八向搜索。可以设置一个八向的常量数组,搜索每一个方向,如果满足条件就递归,否则结束递归。当搜索到第7个单词‘g’时,用vis保存路径,此次DFS也就结束了。
首先在矩阵中搜索,找到y和i相连的方向k,以k方向进行DFS。*/
#include <bits/stdc++.h>
using namespace std;

const int maxn=100+10;
struct node
{
int x,y;
}c[maxn];//记录路径
char fz[maxn][maxn],stand[]="yizhong";//fz保存单词矩阵,stand保存保准的“yizhong”便于匹配
int vis[maxn][maxn];//保存路径,是否该点为答案
int dir[][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};//八向的常量数组
void dfs(int x,int y,node c[],int k,int cur)
{
if(cur==7){
for(int i=0;i<7;i++)
vis[c[i].x][c[i].y]=1;
}
else{
int dx=x+dir[k][0];//沿着正确的k方向搜索
int dy=y+dir[k][1];
if(cur==6||fz[dx][dy]==stand[cur+1]){
c[cur].x=x;c[cur].y=y;
dfs(dx,dy,c,k,cur+1);
}
}
}
int main()
{
freopen("input.txt","r",stdin);
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%s",fz[i]);
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)//搜索y,i相连的可能的方向k,以k为方向进行DFS
for(int j=0;j<n;j++)
if(fz[i][j]=='y') for(int k=0;k<8;k++){
int x=i+dir[k][0];
int y=j+dir[k][1];
if(fz[x][y]=='i')
dfs(i,j,c,k,0);
}
for(int i=0;i<n;i++){//输出结果
for(int j=0;j<n;j++)
if(vis[i][j]) printf("%c",fz[i][j]);
else printf("*");
printf("\n");
}
return 0;
}

单词接龙

题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beastbeast和astonishastonish,如果接成一条龙则变为beastonishbeastonish,另外相邻的两部分不能存在包含关系,例如atat 和 atideatide 间不能相连。

输入格式

输入的第一行为一个单独的整数n(n≤20)表示单词数,以下n 行每行有一个单词,输入的最后一行为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

输出格式

只需输出以此字母开头的最长的“龙”的长度

输入 #1

1
2
3
4
5
6
7
5
at
touch
cheat
choose
tact
a

输出 #1

1
23

说明/提示

(连成的“龙”为atoucheatactactouchoose)

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
/*
首先明确几个要点:
一个单词最多用两次
单词可以不全用完
不可以包含:一旦包含了和不用岂不是一样
按照贪心原则,重叠部分应该越少越好
Talk is cheap, show me the code.
代码结构非常简明,canlink()返回最小重叠部分的长度,没有返回0。solve()进行dfs搜索。主函数读取、调用和输出。
*/
#include<bits/stdc++.h>
using namespace std;
string str[20];
int use[20], length = 0, n;
int canlink(string str1, string str2) {
for(int i = 1; i < min(str1.length(), str2.length()); i++) {//重叠长度从1开始,直到最短的字符串长度-1(因为不能包含)
int flag = 1;
for(int j = 0; j < i; j++)
if(str1[str1.length() - i + j] != str2[j]) flag = 0;//逐个检测是否相等
if(flag) return i;//检测完毕相等则立即return
}
return 0;//无重叠部分,返回0
}
void solve(string strnow, int lengthnow) {
length = max(lengthnow, length);//更新最大长度
for(int i = 0; i < n; i++) {
if(use[i] >= 2) continue;//该字符串使用次数需要小于2
int c = canlink(strnow, str[i]);//获取重叠长度
if(c > 0) {//有重叠部分就开始dfs
use[i]++;
solve(str[i], lengthnow + str[i].length() - c);
use[i]--;
}
}
}
main() {
cin >> n;
for(int i = 0; i <= n; i++) use[i] = 0, cin >> str[i];//str[n]为开始字符
solve(' '+str[n], 1);//有必要解释一下开始阶段。为了指定第一个字符,而且因为canlink需要重叠部分小于最短长度-1,所以要从前面添加一个无意义充长度的‘ ’。这样就强制了canlink函数比较最后一位。
cout << length ;
}

加分二叉树

题目描述

设一个n个节点的二叉树tree的中序遍历为(1,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第ii个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下:

subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数。

若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树tree。要求输出;

(1)tree的最高加分

(2)tree的前序遍历

输入格式

第1行:1个整数n(n<30),为节点个数。

第2行:n个用空格隔开的整数,为每个节点的分数(分数<100)。

输出格式

第1行:1个整数,为最高加分(Ans ≤4,000,000,000)。

第2行:n个用空格隔开的整数,为该树的前序遍历。

输入

1
2
5
5 7 1 2 10

输出

1
2
145
3 1 2 4 5
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
49
50
/*
树形Dp
因为此树是按照中序输入,先看一下第二个小问,
若要确定前序遍历,那么必须知道树的根结点之后 递归输出;
此时回到第一问就是求到最大加分树之后,就确定了根节点,
那么如何求最大加分树——根据中序的特征,想到以枚举根结点为起点
那么轻易得出如果根结点的编号为x,那么左子树的结点有1~x-1,右子树 结点有x+1~n
根据这样的思路来进行一个递归搜索, 直到得到叶子结点的最优,再逐步推出这个树的每一层的最优,直到根这个结点的最优
即为==>以这个结点为根的最优值,枚举一遍所有结点为根的情况之后,即为答案
*/
#include<iostream>
#include<cmath>
#include<cstdio>
int n;
int f[35];
int s[35][35],p[35][35];
using namespace std;
int dfs(int l,int r)
{
if(l>r)return 1;//如果交叉则说明此结点无儿子,则默认为权值为1
if(l==r){s[l][r]=l;return f[l];}//如果正好只有一个结点的,那么直接返回该结点的值
if(p[l][r])return p[l][r];//①记忆化搜索
int ans=0,num;
for(int k=l;k<=r;k++)//枚举子层次的根节点
{
int t=dfs(l,k-1)*dfs(k+1,r)+f[k];
if(t>ans)
{
ans=t;//取得以此根为结点的权值的最优
num=k;// 标记以在l~r这些子结点之中以num为根是最优结果
}
}
s[l][r]=num;//记忆 num
return p[l][r]=ans;//记忆化
}
void zhao(int l,int r)
{
if(l>r)return;
cout<<s[l][r]<<" ";//输出根
zhao(l,s[l][r]-1);//递归输出左结点
zhao(s[l][r]+1,r);//递归输出右结点
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>f[i];
cout<<dfs(1,n)<<endl;
zhao(1,n);
return 0;
}

数字三角形(杨辉三角形)

Problem

有这么一个游戏:

写出一个1至N 的排列ai,然后每次将相邻两个数相加,构成新的序列,再对新序列进行这样的操作,显然每次构成的序列都比上一次的序列长度少1,直到只剩下一个数字位置。下面是一个例子:

3,1,2,4

4,3,6

7,9

16

最后得到16这样一个数字。

现在想要倒着玩这样一个游戏,如果知道N,知道最后得到的数字的大小sum,请你求出最初序列ai,为1至N的一个排列。若答案有多种可能,则输出最小的那一个。

输入格式

两个正整数n,sum。对于100%的数据,n≤12,sum≤12345。

输出格式

输出包括1行,为最小的那个答案。

当无解的时候,请什么也不输出。(好奇葩啊)

输入 #1

1
4 16

输出 #1

1
3 1 2 4
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
49
/*假设一个排列数字用a,b,c,d....代替,那么它最终的和是有规律的:
如果n为4,那么sum是a+3b+3c+d。
如果n为5,那么sum是a+4b+6c+4d+e。
如果n为6,那么sum是a+5b+10c+10d+5e+f。
即排列到哪个数,我们就能快速算出(O(1))目前为止这个排列最终的和,而不用一步一步模拟求和下去,节省了很多的时间*/
#include<bits/stdc++.h>
using namespace std;
int n,sum,y[20][20],vis[20],a[20],flag;
void dfs(int p,int s){
//结果可能有多种、题目只要求输出一种结果flag为1表示已经找到了一种结果,则可以结束了|如果s已经超出题目要求的sum,则继续递归下去无意义(剪枝)
if(flag||s>sum){
return ;
}
//类似于全排列,如果已经超过搜索步骤(层数)了,就可以结束递归
if(p>n){
//如果步骤到了并且此时的s跟题目所要求的sum相同,则表示搜索到了结果
if(s==sum){
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
flag=1;
}
return;
}
//由于不知道排列顺序,所以需要枚举
for(int i=1;i<=n;i++){
//如果该数未被使用过
if(!vis[i]){
a[p]=i;//记住当前步数用的是这个数
vis[i]=1;//标记为1,防止重复判断
//步骤+1,将这个数字i*和当前步数的数相乘求和进入杨辉三角下一行,
dfs(p+1,s+y[n][p]*i);
vis[i]=0;//回溯
}
}
}
int main(){
cin>>n>>sum;
//先构建杨辉三角形
y[1][1]=1;
for(int i=2;i<=13;i++){
for(int j=1;j<=i;j++){
y[i][j] = y[i-1][j-1]+y[i-1][j];
}
}
//进行搜索
dfs(1,0);
return 0;
}

滑雪

题目描述

Michael 喜欢滑雪。这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子:

1
2
3
4
5
1   2   3   4   5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度会减小。在上面的例子中,一条可行的滑坡为 24-17-16-1(从 24 开始,在 1结束)。当然 25-24-23-…-3-2-1 更长。事实上,这是最长的一条。

输入格式

输入的第一行为表示区域的二维数组的行数 R 和列数 C。下面是 R行,每行有 C 个数,代表高度(两个数字之间用 1 个空格间隔)。对于 100% 的数据,1≤R,C≤100。

输出格式

输出区域中最长滑坡的长度。

输入 #1

1
2
3
4
5
6
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

输出 #1

1
25
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
#include<bits/stdc++.h>
using namespace std;
int a[110][110],r,c,res,dp[110][110];
int xx[] = {1,-1,0,0};
int yy[] = {0,0,-1,1};
//int[][] dir={{1,0},{-1,0},{0,-1},{0,1}};
int dfs(int x,int y){
//剪枝,如果已经存在则直接返回
if(dp[x][y]>0)
return dp[x][y];
int maxn = 1;
for(int i=0;i<4;i++){
//int dx = x+dir[i][0];
//int dy = y+dir[i][1];
int dx = x+xx[i];
int dy = y+yy[i];
//注意这里为什么不需要标记函数?因为a[dx][dy]一旦符合条件就回不了头了
if(dx>=1&&dx<=r&&dy>=1&&dy<=c&&a[dx][dy]<a[x][y]){
maxn = max(maxn,dfs(dx,dy)+1);
}
}
//存进备忘录中
return dp[x][y]=maxn;
}
int main(){
cin>>r>>c;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
cin>>a[i][j];
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
res = max(res,dfs(i,j));
}
}
cout<<res;
return 0;
}

吃奶酪

题目描述

房间里放着 n 块奶酪。一只小老鼠要把它们都吃掉,问至少要跑多少距离?老鼠一开始在 (0,0) 点处。

输入格式

第一行一个正整数 n。1≤n≤15。

接下来每行 2 个实数,表示第i块奶酪的坐标。

输出格式

一个数,表示要跑的最少距离,保留 2 位小数。

输入 #1

1
2
3
4
5
4
1 1
1 -1
-1 1
-1 -1

输出 #1

1
7.41
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
//只能得90分,满分需要进行状态压缩 
#include<bits/stdc++.h>
using namespace std;
int n,vis[20];
double res = 999999999999;
double a[20],b[20];
double dis(int t1,int t2){//算出两个点的距离
return sqrt((a[t1]-a[t2])*(a[t1]-a[t2])+(b[t1]-b[t2])*(b[t1]-b[t2]));
}
void dfs(int p,int cur,double s){
if(n==p){//对p进行边界判断,从0开始,故到n结束
res = min(res,s);
return ;
}
//剪枝 ,对s边界进行判断
if(s>res){
return ;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
vis[i]=1;
dfs(p+1,i,s+dis(cur,i));
vis[i]=0;
}
}

}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i];
//小老鼠吃了的糖果的数目0,当前坐标点0 ,距离 0
dfs(0,0,0);
printf("%.2lf",res);
return 0;
}

数独

输入: 一个未填的数独

1
2
3
4
5
6
7
8
9
8 0 0 0 0 0 0 0 0 
0 0 3 6 0 0 0 0 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
0 0 0 0 4 5 7 0 0
0 0 0 1 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
0 9 0 0 0 0 4 0 0

输出: 填好的数独

1
2
3
4
5
6
7
8
9
8 1 2 7 5 3 6 4 9 
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2
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
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
//mp是读入的数独数组,vx是每一行,vy是每一列,vc是每一个小九宫格
int mp[10][10],vx[10][10],vy[10][10],vc[10][10];
void dfs(int x,int y){
if(x==9){//表示已经全部搜索完成,直接打印输出
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
cout<<mp[i][j]<<" ";
}
cout<<endl;
}
return ;
}
if(y==9){//从这一行的最后一个位置跳转到下一行第一个位置
dfs(x+1,0);
}
if(mp[x][y])//如果已经存在,则直接搜索下一个位置
dfs(x,y+1);
else{
//枚举1~9
for(int i=1;i<10;i++){
//如果每一行、每一列、每一个九宫格i都还未被存进
if(!vx[x][i]&&!vy[y][i]&&!vc[x/3*3+y/3][i]){
vx[x][i]=1;
vy[y][i]=1;
vc[x/3*3+y/3][i]=1;
mp[x][y]=i;//注意mp要读入数据,为了到时候搜索完成直接输出

dfs(x,y+1);

mp[x][y]=0;//回溯,注意点
vx[x][i]=0;
vy[y][i]=0;
vc[x/3*3+y/3][i]=0;
}
}
}
}
int main(){
int tmp;
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
cin>>tmp;
mp[i][j] = tmp;
vx[i][tmp]=1;//读入数据时顺便标记
vy[j][tmp]=1;
vc[i/3*3+j/3][tmp]=1;
}
}
dfs(0,0);
return 0;
}

靶型数独

img

Problem

比赛的要求是:每个人必须完成一个给定的数独(每个给定数独可能有不同的填法),而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和

总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图,在以下的这个已经填完数字的靶形数独游戏中,总分数为 2829。游戏规定,将以总分数的高低决出胜负。

输入格式

一共 9 行。每行 9 个整数(每个数都在 0∼9 的范围内),表示一个尚未填满的数独方格,未填的空格用“0”表示。每两个数字之间用一个空格隔开。对于 100% 的数据,数独中非 0 数的个数不少于 24。

输出格式

输出共 1 行。输出可以得到的靶形数独的最高分数。如果这个数独无解,则输出整数 -1。

输入 #1

1
2
3
4
5
6
7
8
9
7 0 0 9 0 0 0 0 1 
1 0 0 0 0 5 9 0 0
0 0 0 2 0 0 0 8 0
0 0 5 0 2 0 0 0 3
0 0 0 0 0 0 6 4 8
4 1 3 0 0 0 0 0 0
0 0 7 0 0 2 0 9 0
2 0 1 0 6 0 8 0 4
0 8 0 5 0 4 0 1 2

输出 #1

1
2829

输入 #2

1
2
3
4
5
6
7
8
9
0 0 0 7 0 2 4 5 3 
9 0 0 0 0 8 0 0 0
7 4 0 0 0 5 0 1 0
1 9 5 0 8 0 0 0 0
0 7 0 0 0 0 0 2 5
0 3 0 5 7 9 1 0 8
0 0 0 6 0 1 0 0 0
0 6 0 9 0 0 0 0 1
0 0 0 0 0 0 0 0 6

输出 #2

1
2852
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//整体思路就是从已知数字最多的一行开始搜索
#include<bits/stdc++.h>
using namespace std;
//mp是读入的数独数组,vx是每一行,vy是每一列,vc是每一个小九宫格
int mp[10][10],vx[10][10],vy[10][10],vc[10][10],ans=-1;
struct Node{
int num,cnt;
}so[10];
bool cmp(Node x,Node y){
return x.cnt>y.cnt;
}
void dfs(int x,int y){
int sx = x;
x = so[sx].num;
if(sx==9){//表示已经全部搜索完成,直接打印输出
int sum=0;
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
sum+=mp[i][j]*min(10-abs(i-4),10-abs(j-4));
}
}
ans = max(ans,sum);
return ;
}
if(y==9){//从这一行的最后一个位置跳转到下一行第一个位置
dfs(sx+1,0);
return;
}
if(mp[x][y])//如果已经存在,则直接搜索下一个位置
dfs(sx,y+1);
else{
//枚举1~9
for(int i=1;i<10;i++){
//如果每一行、每一列、每一个九宫格i都还未被存进
if(!vx[x][i]&&!vy[y][i]&&!vc[x/3*3+y/3][i]){

vx[x][i]=1;
vy[y][i]=1;
vc[x/3*3+y/3][i]=1;
mp[x][y]=i;//注意mp要读入数据,为了到时候搜索完成直接输出

dfs(sx,y+1);

mp[x][y]=0;//回溯,注意点
vx[x][i]=0;
vy[y][i]=0;
vc[x/3*3+y/3][i]=0;
}
}
}
}
int main(){
int tmp;
for(int i=0;i<9;i++){
so[i].num=i;
for(int j=0;j<9;j++){
cin>>tmp;
mp[i][j] = tmp;
if(tmp){
so[i].cnt++;
vx[i][tmp]=1;//读入数据时顺便标记
vy[j][tmp]=1;
vc[i/3*3+j/3][tmp]=1;
}

}
}
sort(so,so+9,cmp);
dfs(0,0);
cout<<ans;

return 0;
}

挖地雷

题目描述
在一个地图上有N个地窖(N≤20),每个地窖中埋有一定数量的地雷。同时,给出地窖之间的连接路径。当地窖及其连接的数据给出之后,某人可以从任一处开始挖地雷,然后可以沿着指出的连接往下挖(仅能选择一条路径),当无连接时挖地雷工作结束。设计一个挖地雷的方案,使某人能挖到最多的地雷。
输入格式
有若干行。第1行只有一个数字,表示地窖的个数N。第2行有N个数,分别表示每个地窖中的地雷个数。第33行至第N+1行表示地窖之间的连接情况:第3行有n-1个数(0或1),表示第一个地窖至第2个、第3个、…、第n个地窖有否路径连接。如第3行为11000…0,则表示第1个地窖至第2个地窖有路径,至第3个地窖有路径,至第4个地窖、第5个、…、第n个地窖没有路径。第4行有n−2个数,表示第二个地窖至第3个、第4个、…、第n个地窖有否路径连接。… …第n+1行有1个数,表示第n−1个地窖至第n个地窖有否路径连接。(为0表示没有路径,为1表示有路径)。
输出格式
有两行第一行表示挖得最多地雷时的挖地雷的顺序,各地窖序号间以一个空格分隔,不得有多余的空格。第二行只有一个数,表示能挖到的最多地雷数。

输入

1
2
3
4
5
6
15
10 8 4 7 6
1 1 1 0
0 0 0
1 1
1

输出

1
2
11 3 4 5
27
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
49
50
51
#include <iostream>
using namespace std;
int n, mp[30][30], i, j, f[30], p[30], a[30], maxn = 0, maxi;
void dg(int x)
{
if (!x)
{
return;
}
dg(p[x]);
cout << x << " ";
}
int main()
{
cin >> n;
for (i = 1; i <= n; i++)
{
cin >> a[i];
f[i] = a[i];
}
for (i = 1; i < n; i++)
{
for (j = i + 1; j <= n; j++)
{
cin >> mp[i][j];
}
}
for (i = 2; i <= n; i++)
{
for (j = 1; j < i; j++)
{
if (mp[j][i])//注意是从j到i,而不是i到j,方便找出所有地窖中到当前地窖的最大值
{
if (f[i] < f[j] + a[i])
{
f[i] = f[j] + a[i];
p[i] = j; //maxn =j;@1
}
}
}
if (maxn < f[i])
{
maxn = f[i];
maxi = i; //若这个判断在@1处,maxi是记录到i的前驱点中最大地雷数
}
}
dg(maxi);
cout << endl;
cout << maxn << endl;
return 0;
}