【蓝桥杯省赛】冲刺练习题【深搜广搜】倒计时【09】天
目录
demo1
static String b[] = { "a", "b", "c", "d", "e", "f", "g" };
static int [][]arr= {
{0,0,1,1,0,1,0},
{0,0,1,0,0,0,0},
{1,1,0,1,0,0,0},
{1,0,1,0,0,0,0},
{0,0,0,0,0,0,1},
{1,0,0,0,0,0,1},
{0,0,0,0,1,1,0}
};对此二维数组进行深度搜索与广度搜索，并遍历结果。
深搜结果
a c b d f g e 广搜结果
a c d f b g e 深搜的遍历过程就是尽可能深的搜索树的分支，当一个节点的所有子节点都被探寻过了，搜索将回溯到发现该节点的那那条边的起始节点 这个过程会一直持续到已发现节点可到达所有节点为止。 如果还存在未发现的节点则进程会随便选择一个未发现的节点重复以上的过程 整个进程直到所有节点都被访问过为止。
深度优先搜索遍历过程 从a开始搜索可以看到a的子节点有c、d、f系统会依次对其进行深度优先搜索 进程先对c进行子节点的搜索可以看出c有两个子节点b、d 可以看出b没有子节点了，但是d节点作为c的子节点还没有被访问所有这个时候程序会走到d的位置 但是d也没有子节点这个时候进程会回溯到发现d的这条边的起始节点a的位置然后在对其进行搜索 a的子节点中只有f没有被遍历了所以进程只能进到f的位置然后在对其进行遍历可以看出f的两个子节点也没有子节点 所以进程在对g、e进行完遍历之后进程结束
广度优先搜索 和深搜不同广搜会沿着树的高度和宽度对节点进行依次遍历 从树的根节点a开始，会发现a的子节点有c、d、f三个子节点，进程会先对这三个节点进行访问然后再访问其的子节点 对c、d、f完成访问之后进行则会探寻这三个节点的子节点并对其进行遍历，可以从图中看出他们的子节点有c、g、e 可以看出c、g、e没有子节点了所以程序对其遍历之后随之结束
深搜代码
public class dfs {
// 构造图的边
private int[][] edges = {
{0,0,1,1,0,1,0},
{0,0,1,0,0,0,0},
{1,1,0,1,0,0,0},
{1,0,1,0,0,0,0},
{0,0,0,0,0,0,1},
{1,0,0,0,0,0,1},
{0,0,0,0,1,1,0}
};
// 构造图的顶点
private String[] vertexs = { "a", "b", "c", "d", "e", "f", "g" };
// 记录被访问顶点
private boolean[] verStatus;
// 顶点个数
private int vertexsNum = vertexs.length;
public void DFSTra() {
verStatus = new boolean[vertexsNum];
for (int i = 0; i < vertexsNum; i++) {
if (verStatus[i] == false) {
DFS(i);
}
}
}
// 递归深搜
private void DFS(int i) {
System.out.print(vertexs[i] + " ");
verStatus[i] = true;
//深度搜索子节点
for (int j = firstAdjVex(i); j >= 0; j = nextAdjvex(i, j)) {
if (!verStatus[j]) {
DFS(j);
}
}
}
// 返回与i相连的第一个顶点
private int firstAdjVex(int i) {
for (int j = 0; j < vertexsNum; j++) {
if (edges[i][j] > 0) {
return j;
}
}
return -1;
}
// 返回与i相连的下一个顶点
private int nextAdjvex(int i, int k) {
for (int j = (k + 1); j < vertexsNum; j++) {
if (edges[i][j] == 1) {
return j;
}
}
return -1;
}
// 测试
public static void main(String[] args) {
new dfs().DFSTra();
}
}广搜代码
import java.util.LinkedList;
import java.util.Queue;
public class bfs {
// 构造图的边
private int[][] edges = {
{0,0,1,1,0,1,0},
{0,0,1,0,0,0,0},
{1,1,0,1,0,0,0},
{1,0,1,0,0,0,0},
{0,0,0,0,0,0,1},
{1,0,0,0,0,0,1},
{0,0,0,0,1,1,0}
};
// 构造图的顶点
private String[] vertexs = { "a", "b", "c", "d", "e", "f", "g" };
// 记录被访问顶点
private boolean[] verStatus;
// 顶点个数
private int vertexsNum = vertexs.length;
// 广搜
private void BFS() {
verStatus = new boolean[vertexsNum];
Queue<Integer> temp = new LinkedList<Integer>();
//遍历每个节点
for (int i = 0; i < vertexsNum; i++) {
//判断当前节点是否被访问过
if (!verStatus[i]) {//如果没有被访问的话则将其加入队列
System.out.print(vertexs[i] + " ");
verStatus[i] = true;
temp.offer(i);
while (!temp.isEmpty()) {
//将最先进入队列的节点移除
int j = temp.poll();
//广度搜索子节点
for (int k = firstAdjvex(j); k >= 0; k = nextAdjvex(j, k)) {
if (!verStatus[k]) {
System.out.print(vertexs[k] + " ");
verStatus[k] = true;
temp.offer(k);
}
}
}
}
}
}
// 返回与i相连的第一个顶点
private int firstAdjvex(int i) {
for (int j = 0; j < vertexsNum; j++) {
if (edges[i][j] > 0) {
return j;
}
}
return -1;
}
// 返回与i相连的下一个顶点
private int nextAdjvex(int i, int k) {
for (int j = (k + 1); j < vertexsNum; j++) {
if (edges[i][j] > 0) {
return j;
}
}
return -1;
}
// 测试
public static void main(String args[]) {
new bfs().BFS();
}
}demo2
static int[][] nums = {
{ 0 , 1 , 0 , 0 , 0 , 0 , 0, 1 , 0},
{ 1 , 0, 1 ,0 , 1 , 0 , 0 , 0 , 0},
{ 0 , 1 , 0 , 1 , 0 ,0 , 0 , 0 , 0},
{ 0 , 0 , 1 , 0 , 1 , 1 , 0 , 0 ,0},
{ 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0},
{ 0 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 0},
{ 0 , 0 , 0 , 0 , 0 , 1, 0 , 0 , 0},
{ 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1},
{ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0}
};
static String res[] = {"1","2","3","4","5","6","7","8","9" };对此二维数组进行深度搜索与广度搜索，并遍历结果。
深搜结果
1 2 3 4 5 6 7 8 9 广搜结果
1 2 8 3 5 6 9 4 7 深搜的遍历过程就是尽可能深的搜索树的分支，当一个节点的所有子节点都被探寻过了，搜索将回溯到发现该节点的那那条边的起始节点 这个过程会一直持续到已发现节点可到达所有节点为止。 如果还存在未发现的节点则进程会随便选择一个未发现的节点重复以上的过程 整个进程直到所有节点都被访问过为止。
深搜遍历过程 从1开始搜索可以看到1的子节点有2、8两个，进程会依次对其进行深度优先搜索 进程先对2进行子节点的搜索可以看出2也有两个子节点3、5 然后进程又会对3进行子节点的搜索可以看出只有一个子节点4，而4没有子节点了这个时候进程就会回溯到2的位置然后对5进行子节点的搜索 可以看出5的子节点也是只有一个4，但是这个时候5还有一个父节点6没有被访问所以进程不会回溯到2的位置 而是对6进行子节点的搜索，6的子节点只有一个7这个时候进程又会发现6有父节点8没有访问过 所以进程会对8再次再次进行子节点的搜索，发现子节点只有6和9但是6已经访问过了，而9也没有子节点 到这里树的所有节点就完成了全部的探索了
广搜遍历过程 和深搜不同广搜会沿着树的高度和宽度对节点进行依次遍历 从树的根节点1开始，会发现1的子节点有2、8两个子节点，进程会先对这两个节点进行访问然后再访问其的子节点 对2、8完成访问之后进行则会探寻这两个节点的子节点并对其进行遍历，可以从图中看出他们的子节点有3、5、6、9 然后进程对着4个节点完成遍历之后会再次探寻其的子节点可以看出只有4和7了且无子节点 在对4和7完成遍历之后整个进程也就随之结束了
深搜代码
public class dfs {
// 构造图的边
private int[][] edges = {
{ 0 , 1 , 0 , 0 , 0 , 0 , 0, 1 , 0},
{ 1 , 0, 1 ,0 , 1 , 0 , 0 , 0 , 0},
{ 0 , 1 , 0 , 1 , 0 ,0 , 0 , 0 , 0},
{ 0 , 0 , 1 , 0 , 1 , 1 , 0 , 0 ,0},
{ 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0},
{ 0 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 0},
{ 0 , 0 , 0 , 0 , 0 , 1, 0 , 0 , 0},
{ 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1},
{ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0}
};
// 构造图的顶点
private String[] vertexs = {"1","2","3","4","5","6","7","8","9"};
// 记录被访问顶点
private boolean[] verStatus;
// 顶点个数
private int vertexsNum = vertexs.length;
public void DFSTra() {
verStatus = new boolean[vertexsNum];
for (int i = 0; i < vertexsNum; i++) {
if (verStatus[i] == false) {
DFS(i);
}
}
}
// 递归深搜
private void DFS(int i) {
System.out.print(vertexs[i] + " ");
verStatus[i] = true;
//深度搜索子节点
for (int j = firstAdjVex(i); j >= 0; j = nextAdjvex(i, j)) {
if (!verStatus[j]) {
DFS(j);
}
}
}
// 返回与i相连的第一个顶点
private int firstAdjVex(int i) {
for (int j = 0; j < vertexsNum; j++) {
if (edges[i][j] > 0) {
return j;
}
}
return -1;
}
// 返回与i相连的下一个顶点
private int nextAdjvex(int i, int k) {
for (int j = (k + 1); j < vertexsNum; j++) {
if (edges[i][j] == 1) {
return j;
}
}
return -1;
}
// 测试
public static void main(String[] args) {
new dfs().DFSTra();
}
}广搜代码
import java.util.LinkedList;
import java.util.Queue;
public class bfs {
// 构造图的边
private int[][] edges = {
{ 0 , 1 , 0 , 0 , 0 , 0 , 0, 1 , 0},
{ 1 , 0, 1 ,0 , 1 , 0 , 0 , 0 , 0},
{ 0 , 1 , 0 , 1 , 0 ,0 , 0 , 0 , 0},
{ 0 , 0 , 1 , 0 , 1 , 1 , 0 , 0 ,0},
{ 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0},
{ 0 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 0},
{ 0 , 0 , 0 , 0 , 0 , 1, 0 , 0 , 0},
{ 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1},
{ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0}
};
// 构造图的顶点
private String[] vertexs = {"1","2","3","4","5","6","7","8","9"};
// 记录被访问顶点
private boolean[] verStatus;
// 顶点个数
private int vertexsNum = vertexs.length;
// 广搜
private void BFS() {
verStatus = new boolean[vertexsNum];
Queue<Integer> temp = new LinkedList<Integer>();
//遍历每个节点
for (int i = 0; i < vertexsNum; i++) {
//判断当前节点是否被访问过
if (!verStatus[i]) {//如果没有被访问的话则将其加入队列
System.out.print(vertexs[i] + " ");
verStatus[i] = true;
temp.offer(i);
while (!temp.isEmpty()) {
//将最先进入队列的节点移除
int j = temp.poll();
//广度搜索子节点
for (int k = firstAdjvex(j); k >= 0; k = nextAdjvex(j, k)) {
if (!verStatus[k]) {
System.out.print(vertexs[k] + " ");
verStatus[k] = true;
temp.offer(k);
}
}
}
}
}
}
// 返回与i相连的第一个顶点
private int firstAdjvex(int i) {
for (int j = 0; j < vertexsNum; j++) {
if (edges[i][j] > 0) {
return j;
}
}
return -1;
}
// 返回与i相连的下一个顶点
private int nextAdjvex(int i, int k) {
for (int j = (k + 1); j < vertexsNum; j++) {
if (edges[i][j] > 0) {
return j;
}
}
return -1;
}
// 测试
public static void main(String args[]) {
new bfs().BFS();
}
}demo3
static int[][] nums = {
{ 0 , 1 , 1 , 1 , 0 , 0 , 0},
{ 1 , 0 , 1 , 0 , 0 , 1 , 0},
{ 1 , 1 , 0 , 1 , 1 , 0 , 0},
{ 1 , 0 , 1 , 0 , 0 , 0 , 1},
{ 0 , 0 , 1 , 0 , 0 , 0 , 0},
{ 0 , 1 , 0 , 0 , 0 , 0 , 1},
{ 0 , 0 , 0 , 1 , 0 , 1 , 0},
};
static String res[] = { "v1", "v2", "v3", "v4", "v5", "v6", "v7" };对此二维数组进行深度搜索与广度搜索，并遍历结果。
深搜结果
v1 v2 v3 v4 v7 v6 v5 广搜结果
v1 v2 v3 v4 v6 v5 v7 深搜的遍历过程就是尽可能深的搜索树的分支，当一个节点的所有子节点都被探寻过了，搜索将回溯到发现该节点的那那条边的起始节点 这个过程会一直持续到已发现节点可到达所有节点为止。 如果还存在未发现的节点则进程会随便选择一个未发现的节点重复以上的过程 整个进程直到所有节点都被访问过为止。
深搜遍历过程 从v1开始搜索可以看到a的子节点有v2、v3、v4系统会依次对其进行深度优先搜索 进程先对v2进行子节点的搜索可以看出v2有两个子节点v3、v4 进程会先对v3进行遍历会发现v3的子节点只有v4，然后v4只有一个子节点v7 进程遍历到v7的时候因为v7还有一个父节点v6没有被访问所以进程会走到v6的位置因为v6的根节点已经遍历了 所以进程会返回到发现v6这条边的起始点也就是v1，但是这个时候还有节点没有被遍历所以 进程会随便选择一个未发现的节点进入然后遍历从图中看出只有v5没有遍历了所以 对v5进行遍历之后进程也就随之结束了
广搜遍历过程 和深搜不同广搜会沿着树的高度和宽度对节点进行依次遍历 从树的根节点v1开始，会发现v1的子节点有v2、v3、v4三个子节点，进程会先对这三个节点进行访问然后再遍历其的子节点 对v2、v3、v4完成访问之后则会探寻这三个节点的子节点并对其进行遍历，可以从图中看出他们未访问的子节点只有v6、v5、v7 而v6、v7、v5没有子节点了所以程序对其遍历之后随之结束
深搜代码
public class dfs {
private int[][] edges = {
{ 0 , 1 , 1 , 1 , 0 , 0 , 0},
{ 1 , 0 , 1 , 0 , 0 , 1 , 0},
{ 1 , 1 , 0 , 1 , 1 , 0 , 0},
{ 1 , 0 , 1 , 0 , 0 , 0 , 1},
{ 0 , 0 , 1 , 0 , 0 , 0 , 0},
{ 0 , 1 , 0 , 0 , 0 , 0 , 1},
{ 0 , 0 , 0 , 1 , 0 , 1 , 0},
};
// 构造图的顶点
private String[] vertexs = {"v1", "v2", "v3", "v4", "v5", "v6", "v7"};
// 记录被访问顶点
private boolean[] verStatus;
// 顶点个数
private int vertexsNum = vertexs.length;
public void DFSTra() {
verStatus = new boolean[vertexsNum];
for (int i = 0; i < vertexsNum; i++) {
if (verStatus[i] == false) {
DFS(i);
}
}
}
// 递归深搜
private void DFS(int i) {
System.out.print(vertexs[i] + " ");
verStatus[i] = true;
//深度搜索子节点
for (int j = firstAdjVex(i); j >= 0; j = nextAdjvex(i, j)) {
if (!verStatus[j]) {
DFS(j);
}
}
}
// 返回与i相连的第一个顶点
private int firstAdjVex(int i) {
for (int j = 0; j < vertexsNum; j++) {
if (edges[i][j] > 0) {
return j;
}
}
return -1;
}
// 返回与i相连的下一个顶点
private int nextAdjvex(int i, int k) {
for (int j = (k + 1); j < vertexsNum; j++) {
if (edges[i][j] == 1) {
return j;
}
}
return -1;
}
// 测试
public static void main(String[] args) {
new dfs().DFSTra();
}
}广搜代码
import java.util.LinkedList;
import java.util.Queue;
public class bfs {
// 构造图的边
private int[][] edges = {
{ 0 , 1 , 1 , 1 , 0 , 0 , 0},
{ 1 , 0 , 1 , 0 , 0 , 1 , 0},
{ 1 , 1 , 0 , 1 , 1 , 0 , 0},
{ 1 , 0 , 1 , 0 , 0 , 0 , 1},
{ 0 , 0 , 1 , 0 , 0 , 0 , 0},
{ 0 , 1 , 0 , 0 , 0 , 0 , 1},
{ 0 , 0 , 0 , 1 , 0 , 1 , 0},
};
// 构造图的顶点
private String[] vertexs = {"v1", "v2", "v3", "v4", "v5", "v6", "v7"};
// 记录被访问顶点
private boolean[] verStatus;
// 顶点个数
private int vertexsNum = vertexs.length;
// 广搜
private void BFS() {
verStatus = new boolean[vertexsNum];
Queue<Integer> temp = new LinkedList<Integer>();
//遍历每个节点
for (int i = 0; i < vertexsNum; i++) {
//判断当前节点是否被访问过
if (!verStatus[i]) {//如果没有被访问的话则将其加入队列
System.out.print(vertexs[i] + " ");
verStatus[i] = true;
temp.offer(i);
while (!temp.isEmpty()) {
//将最先进入队列的节点移除
int j = temp.poll();
//广度搜索子节点
for (int k = firstAdjvex(j); k >= 0; k = nextAdjvex(j, k)) {
if (!verStatus[k]) {
System.out.print(vertexs[k] + " ");
verStatus[k] = true;
temp.offer(k);
}
}
}
}
}
}
// 返回与i相连的第一个顶点
private int firstAdjvex(int i) {
for (int j = 0; j < vertexsNum; j++) {
if (edges[i][j] > 0) {
return j;
}
}
return -1;
}
// 返回与i相连的下一个顶点
private int nextAdjvex(int i, int k) {
for (int j = (k + 1); j < vertexsNum; j++) {
if (edges[i][j] > 0) {
return j;
}
}
return -1;
}
// 测试
public static void main(String args[]) {
new bfs().BFS();
}
}demo4
static int[][] nums = {
{ 0 , 1 , 1 , 0 ,0 ,0},
{ 1 , 0 ,1 , 1 ,0, 0},
{ 1 , 1 , 0 ,1 , 1 , 0},
{ 0 , 1 , 1 , 0 , 1 , 1},
{ 0 , 0 , 1 , 1 , 0 , 0},
{ 0 , 0 , 0 , 1 , 0 , 0},
};
static String res[] = { "a", "b", "c", "d", "e", "f"};对此二维数组进行深度搜索与广度搜索，并遍历结果。
深搜结果
a b c d e f 广搜结果
a b c d e f 深搜的遍历过程就是尽可能深的搜索树的分支，当一个节点的所有子节点都被探寻过了，搜索将回溯到发现该节点的那那条边的起始节点 这个过程会一直持续到已发现节点可到达所有节点为止。 如果还存在未发现的节点则进程会随便选择一个未发现的节点重复以上的过程 整个进程直到所有节点都被访问过为止。
深搜遍历过程 从a开始搜索可以看到1的子节点有b、c两个，进程会依次对其进行深度优先搜索 进程先对b进行子节点的搜索可以看出b也有两个子节点c、d 然后进程又会对c进行子节点的搜索可以看出它也是有两个子节点d、e 进程又会查找d的子节点可以发现d也有两个子节点e、f 这个时候e和f都没有子节点了树的所有节点也都被遍历了
广搜遍历过程 和深搜不同广搜会沿着树的高度和宽度对节点进行依次遍历 从树的根节点a开始，会发现a的子节点有b、c两个子节点，进程会先对这两个节点进行访问然后再访问其的子节点 对b、c完成遍历之后进行则会探寻这两个节点的子节点并对其进行遍历，可以从图中看出他们未遍历的子节点有d、e 然后进程对着2个节点完成遍历之后会再次探寻其的子节点 可以看出只有一个f了且f没有子节点所以程序对f完成遍历之后整个进程也就随之结束了
深搜代码
public class dfs {
// 构造图的边
private int[][] edges = {
{ 0 , 1 , 1 , 0 ,0 ,0},
{ 1 , 0 ,1 , 1 ,0, 0},
{ 1 , 1 , 0 ,1 , 1 , 0},
{ 0 , 1 , 1 , 0 , 1 , 1},
{ 0 , 0 , 1 , 1 , 0 , 0},
{ 0 , 0 , 0 , 1 , 0 , 0},
};
// 构造图的顶点
private String[] vertexs = { "a", "b", "c", "d", "e", "f"};
// 记录被访问顶点
private boolean[] verStatus;
// 顶点个数
private int vertexsNum = vertexs.length;
public void DFSTra() {
verStatus = new boolean[vertexsNum];
for (int i = 0; i < vertexsNum; i++) {
if (verStatus[i] == false) {
DFS(i);
}
}
}
// 递归深搜
private void DFS(int i) {
System.out.print(vertexs[i] + " ");
verStatus[i] = true;
//深度搜索子节点
for (int j = firstAdjVex(i); j >= 0; j = nextAdjvex(i, j)) {
if (!verStatus[j]) {
DFS(j);
}
}
}
// 返回与i相连的第一个顶点
private int firstAdjVex(int i) {
for (int j = 0; j < vertexsNum; j++) {
if (edges[i][j] > 0) {
return j;
}
}
return -1;
}
// 返回与i相连的下一个顶点
private int nextAdjvex(int i, int k) {
for (int j = (k + 1); j < vertexsNum; j++) {
if (edges[i][j] == 1) {
return j;
}
}
return -1;
}
// 测试
public static void main(String[] args) {
new dfs().DFSTra();
}
}广搜代码
import java.util.LinkedList;
import java.util.Queue;
public class bfs {
// 构造图的边
private int[][] edges = {
{ 0 , 1 , 1 , 0 ,0 ,0},
{ 1 , 0 ,1 , 1 ,0, 0},
{ 1 , 1 , 0 ,1 , 1 , 0},
{ 0 , 1 , 1 , 0 , 1 , 1},
{ 0 , 0 , 1 , 1 , 0 , 0},
{ 0 , 0 , 0 , 1 , 0 , 0},
};
// 构造图的顶点
private String[] vertexs = { "a", "b", "c", "d", "e", "f"};
// 记录被访问顶点
private boolean[] verStatus;
// 顶点个数
private int vertexsNum = vertexs.length;
// 广搜
private void BFS() {
verStatus = new boolean[vertexsNum];
Queue<Integer> temp = new LinkedList<Integer>();
//遍历每个节点
for (int i = 0; i < vertexsNum; i++) {
//判断当前节点是否被访问过
if (!verStatus[i]) {//如果没有被访问的话则将其加入队列
System.out.print(vertexs[i] + " ");
verStatus[i] = true;
temp.offer(i);
while (!temp.isEmpty()) {
//将最先进入队列的节点移除
int j = temp.poll();
//广度搜索子节点
for (int k = firstAdjvex(j); k >= 0; k = nextAdjvex(j, k)) {
if (!verStatus[k]) {
System.out.print(vertexs[k] + " ");
verStatus[k] = true;
temp.offer(k);
}
}
}
}
}
}
// 返回与i相连的第一个顶点
private int firstAdjvex(int i) {
for (int j = 0; j < vertexsNum; j++) {
if (edges[i][j] > 0) {
return j;
}
}
return -1;
}
// 返回与i相连的下一个顶点
private int nextAdjvex(int i, int k) {
for (int j = (k + 1); j < vertexsNum; j++) {
if (edges[i][j] > 0) {
return j;
}
}
return -1;
}
// 测试
public static void main(String args[]) {
new bfs().BFS();
}
}5、剪邮票
有12张连在一起的12生肖的邮票。现在你要从中剪下5张来，要求必须是连着的。（仅仅连接一个角不算相连）比如：
粉红色所示部分就是合格的剪取。 请你计算，一共有多少种不同的剪取方法。 请填写表示方案数目的整数。
基本思路 这个思路是我在网上看到的一个思路，比较容易理解： 先排列，从12个邮票中选5个出来， 然后对每个邮票搜索，同一行，同一列，则表示连接到，如果连接到就定义 该块邮票被访问过，最后判断5个邮票是否都被访问过，是就说明是连通的， 但是这个不是全排列，应该是从12个选5个出来 从12个选5个。判断5个是否相连，符合一个visit设为true，五个true，count++
public class demo {
static int a[] = new int[5]; //放置选出的邮票
public static void main(String[] args) {
int count = 0;
//12里面随机选5个, 从0开始是真的秀。
for (a[0] = 0; a[0] < 12; a[0]++) {
for (a[1] = a[0] + 1; a[1] < 12; a[1]++) {
for (a[2] = a[1] +1 ; a[2] < 12; a[2]++) {
for (a[3] = a[2]+1; a[3] < 12; a[3]++) {
for (a[4] = a[3]+1; a[4] < 12; a[4]++) {
if (judge()) {
count++;
}
}
}
}
}
}
System.out.println(count);
}
//判断，5个都为true就说明答案可行。
private static boolean judge() {
boolean visit[] = new boolean[5];
dfs(visit,0);
return visit[0]&&visit[1]&&visit[2]&&visit[3]&&visit[4];
}
private static void dfs(boolean[] visit, int i) {
visit[i] = true;
for (int j = 0; j < visit.length; j++) {
//在同一行，a[i]/4==a[j]/4判断是在同一行，后面是判断是否相邻。
if (!visit[j]&&(a[i]/4==a[j]/4)&&(a[i]==a[j]+1||a[i]==a[j]-1)) {
dfs(visit, j);
}
//在同一列
if (!visit[j]&&(a[i]==a[j]+4||a[i]==a[j]-4)) {
dfs(visit, j);
}
}
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-03-31，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
