搜索之（DFS，BFS）01

淩亂°似流年 2022-05-17 00:39 176阅读 0赞

关于他们的思想，这里就不再罗嗦了，直接 show you my code ,看题讨论 。

### 文章目录 ###

*   *   *  题目1： 5×5迷宫 + 保存路径
         *   *  解题思路：一看到是求解最短路径，直接BFS，可是怎么存储他所走过的路径呐？说实话，这可难了我老长时间。后来经过我二哥点播，得到了下面的思路。
             *  \*\*BFS的下一层（无论有多少个节点）存储上一层的数组下标即可\*\*，如下图。最后就可以通过数组下标找到上一个经过的节点是什么。最后可以通过递归的形式输出最短路径。
         *  题目2：B - 闪现！ + 分层（输出层数）
         *   *  题目大意：可向前走一步，也可向后走一步，还可以( 向前走两倍的现在步数 )
             *  解题思路：因为我们找的还是最快的方式，所以我们还是采取BFS的策略。这个与上一道题有所不同的是“不用存储所走过的路径”，所以我们只用关注他的层数，最后将层数输出即可 。具体的可看代码。
         *  题目3：C - 不规则的棋盘 + 不同行不同列
         *   *  解题思路：DFS。这道题与八皇后问题相当，就是要让他们不同行不同列，所以可以采取：”将列进行标记，按行进行搜索“，这里需要特别注意的一点是：要正确的解决,\`k < n\`的情况，还是ACMER的那种做法，给一个全局变量，DFS要退出时，给他减一下，最后更加需要注意的是在循环结束的时候还需要往下一行DFS一下才行。（当然还是为了解决\` k < n \` 的情况啦）
         *  题目4：D - 二进制？ + 思维
         *   *  题目大意：这个可以说是我不得不写题目大意的一道题。给一个n，找到一个m 使得他只有0和1组成，且是n的倍数。
             *  解题思路：这个里面，因为由0和1组成的数字是不会重复的，所以就不需要标记了，从1开始将他们一个一个放入队列即可，找到能够整除n的m即可 。

### 题目1： 5×5迷宫 + 保存路径 ###

定义一个二维数组：  
int maze\[5\]\[5\] = \{

0, 1, 0, 0, 0,
    
    0, 1, 0, 1, 0,
    
    0, 0, 0, 0, 0,
    
    0, 1, 1, 1, 0,
    
    0, 0, 0, 1, 0,

\};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，  
只能横着走或竖着走，不能斜着走，  
要求编程序找出从左上角到右下角的最短路线。  
Input  
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。  
Output  
左上角到右下角的最短路径，格式如样例所示。  
Sample Input  
0 1 0 0 0  
0 1 0 1 0  
0 0 0 0 0  
0 1 1 1 0  
0 0 0 1 0  
Sample Output  
(0, 0)  
(1, 0)  
(2, 0)  
(2, 1)  
(2, 2)  
(2, 3)  
(2, 4)  
(3, 4)  
(4, 4)

#### 解题思路：一看到是求解最短路径，直接BFS，可是怎么存储他所走过的路径呐？说实话，这可难了我老长时间。后来经过我二哥点播，得到了下面的思路。 ####

#### **BFS的下一层（无论有多少个节点）存储上一层的数组下标即可**，如下图。最后就可以通过数组下标找到上一个经过的节点是什么。最后可以通过递归的形式输出最短路径。 ####

![这里写图片描述][70]

#include <iostream>
    #include <vector>
    #include <queue>
    #include <stack>
    #include <stdio.h>
    /*根据广度优先搜索的话，搜索到终点时，该路径一定是最短的*/
    using namespace std;
    struct Node
    { 
    	int x, y, before;
    	Node() = default;
    	Node(int _x, int _y, int _index) : x(_x), y(_y), before(_index) { }
    	bool check()
    	{ 
    		if (x < 0 || x > 4 || y < 0 || y > 4)
    			return false;
    		else
    			return true;
    	}
    } result[20];		  //记录路径
    int maze[5][5] = { 0}; //迷宫
    int index = 0;
    bool bfs(Node &start, Node &end)
    { 
    	bool visted[5][5] = { false}; //标记数组
    	int dir[4][2] = { 
    		{ 0, 1},
    		{ 1, 0},
    		{ 0, -1},
    		{ -1, 0}};
    	queue<Node> QQ;
    	QQ.push(start);
    	visted[start.x][start.y] = true;
    	Node Vnow, Vnext;
    	while (!QQ.empty())
    	{ 
    		Vnow = QQ.front();
    		QQ.pop();
    		result[index].x = Vnow.x;
    		result[index].y = Vnow.y;
    		result[index].before = Vnow.before;
    		index++;
    
    		for (int i = 0; i < 4; ++i)
    		{ 
    			Node Vnext(Vnow.x + dir[i][0], Vnow.y + dir[i][1], index - 1);// 注意这里
    
    			if (Vnext.x == end.x && Vnext.y == end.y)
    			{ 
    				result[index].x = end.x;
    				result[index].y = end.y;
    				result[index].before = index - 1;
    				return true;
    			}
    			if (Vnext.check() && !visted[Vnext.x][Vnext.y] && !maze[Vnext.x][Vnext.y])
    			{ 
    				QQ.push(Vnext);
    				visted[Vnext.x][Vnext.y] = true;
    			}
    		}
    	}
    	//数据保证有唯一解
    }
    void output(Node tmp)
    { 
    	if (tmp.before == 0 && tmp.x == 0 && tmp.y == 0)
    	{ 
    		printf("(%d, %d)\n", tmp.x, tmp.y);
    	}
    	else
    	{ 
    		output(result[tmp.before]);
    		printf("(%d, %d)\n", tmp.x, tmp.y);
    	}
    }
    int main(void)
    { 
    	for (int i = 0; i < 5; i++)
    	{ 
    		for (int j = 0; j < 5; j++)
    		{ 
    			cin >> maze[i][j];
    		}
    	}
    	Node start(0, 0, 0);
    	Node end(4, 4, 0);
    	bfs(start, end);
    	output(result[index]);
    }

### 题目2：B - 闪现！ + 分层（输出层数） ###

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

*  Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
 *  Teleporting: FJ can move from any point X to the point 2 × X in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

Input  
Line 1: Two space-separated integers: N and K  
Output  
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.  
Sample Input  
5 17  
Sample Output  
4  
Hint  
The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

#### 题目大意：可向前走一步，也可向后走一步，还可以( 向前走两倍的现在步数 ) ####

#### 解题思路：因为我们找的还是最快的方式，所以我们还是采取BFS的策略。这个与上一道题有所不同的是“不用存储所走过的路径”，所以我们只用关注他的层数，最后将层数输出即可 。具体的可看代码。 ####

![这里写图片描述][70 1]

//思路： 因为是找最值，所以策略是 BFS
    #include <iostream>
    #include <queue>
    #include <string.h>
    using namespace std;
    #define MAX 100001 //草，原来那么多的RuntimeError,全是因为我数组开得太大了造成的，草草草草
    int n = 0, k = 0;
    int result = 0; //存放最终结果
    bool visted[MAX] = { false};
    int BFS(int start) // 1
    { 
    	queue<int> QQ;
    	QQ.push(start);
    	visted[start] = true;
    	int Vnow, Vnext;
    	while (!QQ.empty())
    	{ 
    		int loop_size = QQ.size();
    		for (int j = 0; j < loop_size; j++) //有多少出多少，分层处理
    		{ 
    			Vnow = QQ.front();
    			QQ.pop();
    			for (int i = 0; i < 3; i++)
    			{ 
    				if (i == 0)
    					Vnext = Vnow + 1;
    				if (i == 1)
    					Vnext = Vnow - 1;
    				if (i == 2)
    					Vnext = Vnow * 2;
    				if (Vnext == k)
    					return 0;
    				if ( Vnext >= 0 && Vnext < MAX && visted[Vnext] == false ) //这里最好是先判断出没出界，然后判断访问过没有
    				{ 
    					QQ.push(Vnext);
    					visted[Vnext] = true;
    				}
    			}
    		}
    		result++;
    	}
    }
    int main(void)
    { 
    	while (cin >> n >> k)
    	{ 
    		result = 0;
    		memset(visted, 0, sizeof(visted));
    		if (n >= k)
    		{ 
    			cout << n - k << endl;
    			continue;
    		}
    		BFS(n);
    		cout << result + 1 << endl;
    	}
    	return 0;
    }

### 题目3：C - 不规则的棋盘 + 不同行不同列 ###

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。  
Input  
输入含有多组测试数据。  
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n\*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n  
当为-1 -1时表示输入结束。  
随后的n行描述了棋盘的形状：每行有n个字符，其中 \# 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。  
Output  
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。  
Sample Input  
2 1  
\#.  
.\#  
4 4  
…\#  
…\#.  
.\#…  
\#…  
\-1 -1  
Sample Output  
2  
1

#### 解题思路：DFS。这道题与八皇后问题相当，就是要让他们不同行不同列，所以可以采取：”将列进行标记，按行进行搜索“，这里需要特别注意的一点是：要正确的解决,`k < n`的情况，还是ACMER的那种做法，给一个全局变量，DFS要退出时，给他减一下，最后更加需要注意的是在循环结束的时候还需要往下一行DFS一下才行。（当然还是为了解决`k < n` 的情况啦） ####

//思路： DFS + 不同行不同列
    #include <iostream>
    using namespace std;
    char map[10][10] = { 0};
    int n = 0, k = 0; // n*n 的棋盘，k个棋子
    int count = 0;	// 记录方案数目
    int temp = 0;
    bool col[10] = { false}; //对列进行标记，然后按行进行搜索
    int DFS(int x)
    { 
    	if (temp == k)
    	{ 
    		count++;
    		return 0;
    	}
    	if ( x >= n ) //超出界限
    		return 0;
    	for (int i = 0; i < n; i++) //控制列
    	{ 
    		if (map[x][i] == '#' && col[i] == false)
    		{ 
    			col[i] = true;
    			temp++;
    			DFS(x + 1);
    			col[i] = false;
    			temp--;
    		}
    	}
    	DFS(x + 1);
    	/*为了避免： n= 2,k=1 .# #. 的情况 */
    	return 0;
    }
    int main(void)
    { 
    	while (cin >> n >> k)  
    	{ 
    		if (n == -1 && k == -1)
    			return 0;
    		for (int i = 0; i < n; i++)
    			scanf("%s", map[i]);
    		count = 0;
    		DFS(0); //从第0行开始
    		cout << count << endl;
    	}
    	return 0;
    }

### 题目4：D - 二进制？ + 思维 ###

Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.  
Input  
The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.  
Output  
For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.  
Sample Input  
2  
6  
19  
0  
Sample Output  
10  
100100100100100100  
111111111111111111

#### 题目大意：这个可以说是我不得不写题目大意的一道题。给一个n，找到一个m 使得他只有0和1组成，且是n的倍数。 ####

#### 解题思路：这个里面，因为由0和1组成的数字是不会重复的，所以就不需要标记了，从1开始将他们一个一个放入队列即可，找到能够整除n的m即可 。 ####

#include <iostream>
    #include <queue>
    using namespace std;
    long long n; //输入的 n
    queue<long long> QQ; //rtm，刚开始一直不过，把queue提出来一下就过了，草
    long long BFS(long long start)
    { 
    	QQ.push(start);
    	long long Vnow;
    	while (!QQ.empty())
    	{ 
    		Vnow = QQ.front();
    		QQ.pop();
    		if (Vnow % n == 0)
    			return Vnow;
    		if ((Vnow*10) % n == 0)
    			return Vnow * 10;
    		if ((Vnow*10+1) % n == 0)
    			return Vnow * 10 + 1 ;
    		QQ.push(Vnow * 10);
    		QQ.push(Vnow * 10 + 1);
    	}
    	return 0;
    }
    int main(void)
    { 
    	while (cin >> n && n )
    	{ 
    		while (!QQ.empty())
    		{ 
    			QQ.pop();
    		}
    		cout << BFS(1) << endl;
    	}
    	return 0;
    }

[70]: /images/20220517/bb3f92af284446c5a4ce524bb5cd3e6f.png
[70 1]: /images/20220517/a7043d26d33b4bcaa263b3698ac99bc9.png