文章目录
1. 迷宫问题最短路径
有一个迷宫地图，有一些可达的位置，也有一些不可达的位置（障碍、墙壁、边界）。从一个位置到下一个位置只能通过向上（或者向右、或者向下、或者向左）走一步来实现，从起点出发，如何找到一条到达终点的通路。
- 约定顺时针
DFS未简化版
#include<stdio.h> using namespace std; int p,q,min=99999999; int a[100][100]; // 100行100列的地图 --> 1表示空地， 2障碍物 int v[100][100]; //访问数组 -》 0未访问， 1已访问 void dfs(int x, int y, int step) { if(x==p && y==q ) { if(step<min) min=step; return; // 回溯 } // 顺时针试探 //右 if(a[x][y+1]==1 && v[x][y+1]==0){ v[x][y+1] = 1; dfs(x,y+1, step+1); v[x][y+1] = 0; } //下 if(a[x+1][y]==1 && v[x+1][y]==0){ v[x+1][y] = 1; dfs(x+1,y, step+1); v[x+1][y] = 0; } // 左 if(a[x][y-1]==1 && v[x][y-1]==0){ v[x][y-1] = 1; dfs(x,y-1, step+1); v[x][y-1] = 0; } // 上 if(a[x-1][y]==1 && v[x-1][y]==0){ v[x-1][y] = 1; dfs(x-1,y, step+1); v[x-1][y] = 0; } return; } /** 5 4 1 1 2 1 1 1 1 1 1 1 2 1 1 2 1 1 1 1 1 2 1 1 4 3 */ int main(){ int m,n; scanf("%d %d", &m,&n); for(int i=1; i<=m; i++) for(int j=1; j<=n;j++) scanf("%d",&a[i][j]); //1表示空地， 2障碍物 int startX, startY; scanf("%d %d %d %d", &startX, &startY, &p,&q); v[startX][startY] = 1; dfs(startX,startY,0); printf("%d\n",min); return 0; }
DFS 使用方向数组简化if`语句
#include<stdio.h> using namespace std; int p,q,min=99999999; int a[100][100]; // 100行100列的地图 --> 1表示空地， 2障碍物 int v[100][100]; //访问数组 -》 0未访问， 1已访问 // 方向数组 // x表示行, y表示列 int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; void dfs(int x, int y, int step) { if(x==p && y==q ) { if(step<min) min=step; return; // 回溯 } // 顺时针试探 for(int k=0; k<4; k++){ int tx,ty; tx=x+dx[k], ty=y+dy[k]; if(a[tx][ty]==1 && v[tx][ty]==0){ v[tx][ty] = 1; dfs(tx,ty, step+1); v[tx][ty] = 0; } } return; } /** 5 4 1 1 2 1 1 1 1 1 1 1 2 1 1 2 1 1 1 1 1 2 1 1 4 3 */ int main(){ int m,n; scanf("%d %d", &m,&n); for(int i=1; i<=m; i++) // 初始化地图 for(int j=1; j<=n;j++) scanf("%d",&a[i][j]); //1表示空地， 2障碍物 int startX, startY; scanf("%d %d %d %d", &startX, &startY, &p,&q); v[startX][startY] = 1; dfs(startX,startY,0); printf("%d\n",min); return 0; }
2.蓝桥—数字游戏
问题描述
给定一个1～N的排列a[i]，每次将相邻两个数相加，得到新序列，再对新序列重复这样的操作，显然每次得到的序列都比上一次的序列长度少1，最终只剩一个数字。
例如:
3 1 2 4
4 3 6
7 9
16
现在如果知道N和最后得到的数字sum，请求出最初序列a[i]，为1～N的一个排列。若有多种答案，则输出字典序最小的那一个。数据保证有解。
输入格式
第1行为两个正整数n，sum
输出格式
一个1～N的一个排列
样例输入
4 16
样例输出
3 1 2 4
数据规模和约定
0<n<=10
#include<stdio.h> #include<string.h> #include<math.h> int flag = 0; //找到的满足条件为1，反之则0; void DFS(int arry[], int visited[], int n, int index, int sum) { if(flag==0) { if(index == n) //递归出口; { int arry1[n]; int j = 0; int k = 0; for (j = 0; j<n; j++) { arry1[j] = arry[j]; } for (j = 0; j<n-1; j++) for( k = 0; k<n-1-j; k++) arry1[k] = arry1[k]+arry1[k+1]; if(arry1[0]==sum) { for ( j = 0; j<n; j++) { printf("%d ",arry[j]); } flag = 1; } } } int i = 0; for(i = 1; i<=n; i++) //从1到n，一个个的去试; { if(visited[i] == 0) //开始访问; { arry[index] = i; visited[i] = 1; DFS(arry,visited,n,index+1,sum); visited[i] = 0; } } } int main() { int arry[11]; //用来保存结果的数组; int visited[11] = {0}; //访问过置1，没访问过置0; int n = 0; // 数列长度 int sum = 0; // 结果 scanf("%d %d",&n,&sum); DFS(arry, visited, n, 0, sum); return 0; }
3、单词接龙
问题描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。
输入格式
输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出格式
只需输出以此字母开头的最长的“龙”的长度
样例输入
5
at
touch
cheat
choose
tact
a
样例输出
23
样例说明
连成的“龙”为atoucheatactactouchoose
#include<iostream> #include<string> #include<cstring> #define _for(i,a,b) for(int i=a; i<=b; i++) using namespace std; int ans,n; string s[22]; int v[22]; void dfs(string sa, int l){ ans = max(ans,l); // 遍历搜索 _for(i,1,n){ int p = 1; int la = sa.length(), lb = s[i].length(); while(p<min(la,lb)){ if( ( sa.substr(la-p) == s[i].substr(0,p) ) && (v[i]<2) ){ // 标记 v[i]++; dfs(s[i], l+lb-p); //回溯 v[i]--; break; } p++; } } } int main(){ cin>>n; memset(v,0,sizeof(v)); char t; _for(i,1,n) cin>>s[i]; cin>>t; _for(i,1,n) { if(s[i][0] == t){ v[i]++; dfs(s[i],s[i].length()); v[i]--; } } cout<<ans<<endl; return 0; }
4、全排列
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EE016G2r-1619284130978)(.\pics\image-20210316234228177.png)]
5、八皇后
八皇后问题，是在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？
#include<iostream> #define _for(i,a,b) for(int i=a; i<b; i++) using namespace std; int n, cnt = 0; bool lie[20] = {false}; // 列 bool u[20] = {false}; // 左上到右下 bool v[20] = {false}; // 右上到左下 int a[20]; void dfs(int x){ if(x>n){ cnt++; if(cnt<=3){ _for(i,1,n+1) cout<<a[i]<<' '; cout<<endl; } return ; } // 开始搜索 _for(i,1,n+1){ if( !lie[i] && !u[x-i+n] && !v[x+i] ){ lie[i] = 1; u[x-i+n] = 1; v[x+i] = 1; a[x] = i; dfs(x+1); lie[i] = 0; u[x-i+n] = 0; v[x+i] = 0; } } } int main(){ cin>>n; dfs(1); cout<<cnt<<endl; }
6、单词方阵
给一
n×n的字母方阵，内可能蕴含多个“yizhong”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 8个方向的任一方向，同一单词摆放时不再改变方向，单词与单词之间可以交叉,因此有可能共用字母。输出时，将不是单词的字母用*代替，以突出显示单词。例如：
输入： 8 输出： qyizhong *yizhong gydthkjy gy nwidghji n*i* orbzsfgz oz hhgrhwth h*h* zzzzzozo zo iwdfrgng i*n* yyyygggg yg
输入格式
第一行输入一个数n*。(7≤*n≤100)。
第二行开始输入
n×n的字母矩阵。输出格式
突出显示单词的n \times nn×n矩阵。
输入输出样例
输入 #1复制
7 aaaaaaa aaaaaaa aaaaaaa aaaaaaa aaaaaaa aaaaaaa aaaaaaa
输出 #1复制
* * * * * * *
输入 #2复制
8 qyizhong gydthkjy nwidghji orbzsfgz hhgrhwth zzzzzozo iwdfrgng yyyygggg
输出 #2复制
*yizhong gy n*i* oz h*h* zo i*n* yg
#include<bits/stdc++.h> #define _for(i,a,b) for(int i=a; i<b; i++) #define maxN 105 using namespace std; int n; char a[maxN][maxN]; int v[maxN][maxN]={0}; // 八个方向 int xx[] = {1, 1, 1, 0, 0, -1, -1, -1}; int yy[] = {1, 0, -1, 1, -1, 1, 0, -1}; string yz = "yizhong"; void dfs(int x, int y){ // 对八个方向进行搜索 _for(i,0,8){ int flag = 1; // 对"yizhong"这7个字符进行匹配 _for(j,0,7){ // 单一方向的搜素坐标 int dx = x+j*xx[i]; int dy = y+j*yy[i]; // 不满足条件以及越界 if( dx<1 || dx>n || dy<1 || dy>n || yz[j] != a[dx] [dy]){ flag = 0; break; } } // 记录搜索结果 if(flag==1){ _for(j,0,7){ int dx = x+j*xx[i]; int dy = y+j*yy[i]; v[dx][dy] = 1; } } } } int main(){ cin>>n; _for(i,1,n+1){ _for(j,1,n+1){ cin>>a[i][j]; } } // 开始全局搜索 _for(i,1,n+1){ _for(j,1,n+1){ // 当当前字母是y的时候再对该字母的八个方向进行搜索 if(a[i][j]=='y'){ dfs(i,j); } } } // 打印搜索结果 _for(i,1,n+1){ _for(j,1,n+1){ if(v[i][j]==0){ cout<<'*'; } else cout<<a[i][j]; } cout<<endl; } }
