本文最后更新于 894 天前,其中的信息可能已经有所发展或是发生改变。
原题链接
描述
在图像编码的算法中,需要将一个给定的方形矩阵进行 Z 字形扫描(Zigzag Scan)。
给定一个 n×n 的矩阵,Z 字形扫描的过程如下图所示:
对于下面的 4×4 的矩阵,
| 1 5 3 9 |
| 3 7 5 6 |
| 9 4 6 4 |
| 7 3 1 3 |
对其进行 Z 字形扫描后得到长度为 16 的序列:1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3
。
请实现一个 Z 字形扫描的程序,给定一个 n×n 的矩阵,输出对这个矩阵进行 Z 字形扫描的结果。
输入格式
输入的第一行包含一个整数 nn,表示矩阵的大小。
输入的第二行到第 n+1n+1 行每行包含 nn 个正整数,由空格分隔,表示给定的矩阵。
输出格式
输出一行,包含 n×n 个整数,由空格分隔,表示输入的矩阵经过 ZZ 字形扫描后的结果。
数据范围
1≤n≤500,
矩阵元素为不超过 1000 的正整数。
输入样例:
| 4 |
| 1 5 3 9 |
| 3 7 5 6 |
| 9 4 6 4 |
| 7 3 1 3 |
输出样例:
| 1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3 |
分析
- 该题以Z字形遍历数组,对于奇数和偶数情况下,边界转向复杂
- 扩大原二维数组,使边界转向统一
- 观察旋转方向,设初始方向
dr = 0
- 扩大二维数组,遍历满足在原数组范围内时输出
代码
| #include <bits/stdc++.h> |
| using namespace std; |
| const int N=505; |
| |
| int a[2*N][2*N]; |
| |
| int main(){ |
| int n; |
| scanf("%d",&n); |
| for(int i=0;i<n;i++){ |
| for(int j=0;j<n;j++){ |
| scanf("%d",&a[i][j]); |
| } |
| } |
| int dr=0,dx[]={0,1,1,-1},dy[]={1,-1,0,1}; |
| printf("%d ",a[0][0]); |
| int x=0,y=1; |
| for(int i=0;i<(2*n+1)*n;i++){ |
| if(x<n&&y<n){ |
| printf("%d ",a[x][y]); |
| } |
| int l=x+dx[dr],r=y+dy[dr]; |
| if(dr==0||dr==2||r<0||l<0||r>=n||l>=n){ |
| dr=(dr+1)%4; |
| l=x+dx[dr],r=y+dy[dr]; |
| } |
| x=l,y=r; |
| } |
| return 0; |
| } |
原题链接
描述
一个楼梯共有 n 级台阶,每次可以走一级或者两级或者三级,问从第 0 级台阶走到第 n 级台阶一共有多少种方案。
输入格式
一个整数 N。
输出格式
一个整数,表示方案总数。
数据范围
1≤N≤20
输入样例:
输出样例:
分析
代码
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| int n,ans; |
| |
| void dfs(int u){ |
| |
| if(u==n) ans++; |
| |
| |
| if(u+1<=n) dfs(u+1); |
| if(u+2<=n) dfs(u+2); |
| if(u+3<=n) dfs(u+3); |
| |
| } |
| |
| int main(){ |
| |
| cin>>n; |
| |
| dfs(0); |
| |
| cout<<ans<<endl; |
| |
| return 0; |
| } |
搜索是基本的编程技术,在算法竞赛学习中是基础的基础。
分类
- DFS
- BFS
- A* (BFS+贪心)
- 双向广搜
- 双端队列广搜
- 双向DFS
- IDDFS (DFS+BFS)
- IDA* (IDDFS优化)
搜索常使用的算法是BFS和DFS,BFS用队列、DFS用递归来具体实现。在BFS和DFS的基础上可以扩展出A*算法、双向广搜算法、迭代加深搜索、IDA等技术。
思想
- 搜索技术是“暴力法”算法思想的具体实现
- 将所有可能的情况都罗列出来,然后逐一检查,从中找到答案
特点
- 很多问题只能用暴力法解决,例如猜密码,走迷宫等问题
- 对于小规模的问题,暴力法完全够用,而且避免了高级算法需要的复杂编码
- 把暴力法当作参照(benchmark)。拿到题目后,如果没有其他思路,可以先试试暴力法,在具体编程时常常需要对暴力法进行优化,以减少搜索空间,提高效率。
特点
eg:
| #include <iostream> |
| #include <string> |
| #include <queue> |
| using namespace std; |
| |
| struct point{ |
| int x,y; |
| }; |
| |
| int main() { |
| |
| queue<int> a; |
| queue<string> b; |
| queue<point> c; |
| |
| return 0; |
| |
| } |
语法:.push()
eg:
| #include <iostream> |
| #include <string> |
| #include <queue> |
| using namespace std; |
| |
| struct point{ |
| int x,y; |
| }; |
| |
| int main() { |
| |
| queue<int> a; |
| queue<string> b; |
| queue<point> c; |
| |
| a.push(1); |
| |
| b.push("abc"); |
| |
| point p; |
| p.x=10; |
| p.y=20; |
| c.push(p); |
| |
| c.push({10,20}); |
| |
| return 0; |
| |
| } |
语法:.pop()
eg:
| #include <iostream> |
| #include <string> |
| #include <queue> |
| using namespace std; |
| |
| struct point{ |
| int x,y; |
| }; |
| |
| int main() { |
| |
| queue<int> a; |
| queue<string> b; |
| queue<point> c; |
| |
| a.push(1); |
| |
| b.push("abc"); |
| |
| point p; |
| p.x=10; |
| p.y=20; |
| c.push(p); |
| |
| c.push({10,20}); |
| |
| |
| |
| |
| |
| |
| |
| a.pop(); |
| b.pop(); |
| c.pop(); |
| |
| return 0; |
| |
| } |
语法:.size()
eg:
| #include <iostream> |
| #include <string> |
| #include <queue> |
| using namespace std; |
| |
| struct point{ |
| int x,y; |
| }; |
| |
| int main() { |
| |
| queue<int> a; |
| queue<string> b; |
| queue<point> c; |
| |
| a.push(1); |
| |
| b.push("abc"); |
| b.push("cdef"); |
| |
| point p; |
| p.x=10; |
| p.y=20; |
| c.push(p); |
| |
| c.push({10,20}); |
| |
| while(c.size()){ |
| c.pop(); |
| } |
| |
| |
| |
| |
| |
| |
| |
| cout<<a.size()<<endl; |
| cout<<b.size()<<endl; |
| cout<<c.size()<<endl; |
| |
| return 0; |
| |
| } |
语法:.empty()
eg:
| #include <iostream> |
| #include <string> |
| #include <queue> |
| using namespace std; |
| |
| struct point{ |
| int x,y; |
| }; |
| |
| int main() { |
| |
| queue<int> a; |
| queue<string> b; |
| queue<point> c; |
| |
| a.push(1); |
| |
| b.push("abc"); |
| b.push("cdef"); |
| |
| point p; |
| p.x=10; |
| p.y=20; |
| c.push(p); |
| |
| c.push({10,20}); |
| |
| while(!c.empty()){ |
| c.pop(); |
| } |
| |
| |
| |
| |
| |
| |
| |
| cout<<a.empty()<<endl; |
| cout<<b.empty()<<endl; |
| cout<<c.empty()<<endl; |
| |
| return 0; |
| |
| } |
- 当题目需要对一组数据进行扩展式搜索时可以考虑
BFS
- 搜索时要将已经满足要求的点入队
- 不断地弹出队头,以队头元素进行扩展搜索,可以得到若干新的元素
- 对这些元素进行判断,满足继续搜索的条件则将该元素入队,否则具体问题具体分析,标记或抛弃。
- 一般来说,
BFS
在第一次搜到答案时可以直接返回值,提前结束搜索
原题链接
描述
小明现在在玩一个游戏,游戏来到了教学关卡,迷宫是一个N*M的矩阵。
小明的起点在地图中用“S”来表示,终点用“E”来表示,障碍物用“#”来表示,空地用“.”来表示。
障碍物不能通过。小明如果现在在点(x,y)处,那么下一步只能走到相邻的四个格子中的某一个:(x+1,y),(x-1,y),(x,y+1),(x,y-1);
小明想要知道,现在他能否从起点走到终点。
输入格式:
本题包含多组数据。
每组数据先输入两个数字N,M
接下来N行,每行M个字符,表示地图的状态。
数据范围:
2<=N,M<=500
保证有一个起点S,同时保证有一个终点E.
输出格式:
每组数据输出一行,如果小明能够从起点走到终点,那么输出Yes,否则输出No
输入样例:
输出样例
分析
- 走出迷宫需要对每一个点进行搜索
- 首先需要记录
S
的坐标
- 从
S
开始搜索,需要偏移量数组
- 对于
BFS
在搜随时,若搜到E
点直接返回
BFS代码
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| const int N=510; |
| |
| int n,m; |
| |
| char mp[N][N]; |
| |
| bool vis[N][N]; |
| |
| int s1,s2; |
| |
| int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; |
| |
| struct point{ |
| int x,y; |
| }; |
| |
| bool bfs(){ |
| |
| queue<point> st; |
| |
| st.push({s1,s2}); |
| vis[s1][s2]=1; |
| |
| while(!st.empty()){ |
| |
| auto p=st.front(); |
| st.pop(); |
| |
| for(int i=0;i<4;i++){ |
| |
| int l=p.x+dx[i],r=p.y+dy[i]; |
| if(l>=1&&l<=n&&r>=1&&r<=m&&!vis[l][r]&&mp[l][r]!='#'){ |
| if(mp[l][r]=='E') return 1; |
| vis[l][r]=1; |
| st.push({l,r}); |
| } |
| |
| } |
| |
| } |
| |
| return 0; |
| |
| } |
| |
| int main(){ |
| |
| while(cin>>n>>m){ |
| |
| |
| memset(vis,0,sizeof vis); |
| memset(mp,0,sizeof mp); |
| |
| for(int i=1;i<=n;i++){ |
| for(int j=1;j<=m;j++){ |
| cin>>mp[i][j]; |
| if(mp[i][j]=='S'){ |
| s1=i; |
| s2=j; |
| } |
| } |
| } |
| |
| if(bfs()) cout<<"Yes"<<endl; |
| else cout<<"No"<<endl; |
| |
| } |
| |
| return 0; |
| |
| } |
原题链接
描述
给定一个 n×m 的二维整数数组,用来表示一个迷宫,数组中只包含 0 或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。
最初,有一个人位于左上角 (1,1) 处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问,该人从左上角移动至右下角 (n,m) 处,至少需要移动多少次。
数据保证 (1,1) 处和 (n,m) 处的数字为 0,且一定至少存在一条通路。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行,每行包含 m 个整数(0 或 1),表示完整的二维数组迷宫。
输出格式
输出一个整数,表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤100
输入样例:
| 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 |
输出样例:
代码
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| const int N=110; |
| |
| int mp[N][N]; |
| |
| bool vis[N][N]; |
| |
| int ans[N][N]; |
| |
| int n,m; |
| |
| struct point{ |
| int x,y; |
| }; |
| |
| int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; |
| |
| int bfs(){ |
| |
| queue<point> st; |
| st.push({1,1}); |
| vis[1][1]=1; |
| |
| while(!st.empty()){ |
| |
| auto p=st.front(); |
| st.pop(); |
| |
| for(int i=0;i<4;i++){ |
| |
| int l=p.x+dx[i],r=p.y+dy[i]; |
| if(l>=1&&l<=n&&r>=1&&r<=m&&mp[l][r]==0&&!vis[l][r]){ |
| ans[l][r]=ans[p.x][p.y]+1; |
| if(l==n&&r==m) return ans[n][m]; |
| vis[l][r]=1; |
| st.push({l,r}); |
| } |
| |
| } |
| |
| } |
| |
| return ans[n][m]; |
| |
| } |
| |
| int main(){ |
| |
| cin>>n>>m; |
| |
| for(int i=1;i<=n;i++){ |
| for(int j=1;j<=m;j++){ |
| cin>>mp[i][j]; |
| } |
| } |
| |
| cout<<bfs()<<endl; |
| |
| return 0; |
| |
| } |
- 栈是一种先进后出的数据结构
- 只允许对栈顶元素操作,不允许遍历
- 在计算机编程教材中都会提到递归的概念和应用,一般会用数学中的递推方程来讲递归的概念
- 在计算机系统中,递归是通过嵌套来实现的,涉及指针、地址、栈的使用。
- 从算法思想上看,递归是把大问题逐步缩小,直到变成最小的同类问题的过程
- 在递归的过程中,一个递归函数直接调用自己,将数据暂存于栈中是入栈过程,满足条件时返回是出栈过程
例题1 计算n的阶乘
eg:
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| int n; |
| |
| int fx(int u){ |
| |
| |
| |
| if(u==1){ |
| return 1; |
| } |
| |
| return fx(u-1)*u; |
| |
| } |
| |
| int main(){ |
| |
| cin>>n; |
| |
| cout<<fx(n)<<endl; |
| |
| return 0; |
| |
| } |
例题2 走方格
原题链接
描述
给定一个 n×m 的方格阵,沿着方格的边线走,从左上角 (0,0) 开始,每次只能往右或者往下走一个单位距离,问走到右下角 (n,m) 一共有多少种不同的走法。
输入
共一行,包含两个整数 n 和 m。
数据范围
0≤n,m≤10
输出
共一行,包含一个整数,表示走法数量。
样例输入
样例输出
分析
- 每次前进,都有两种方式可选
- 利用递归,产生不同的分支实现两种选择
- 当任意一个分支走到了终点,则为一种走法
代码
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| int n,m; |
| |
| int ans; |
| |
| void step(int x,int y){ |
| |
| if(x==n&&y==m) ans++; |
| |
| |
| if(x+1<=n) step(x+1,y); |
| if(y+1<=m) step(x,y+1); |
| |
| } |
| |
| int main(){ |
| |
| cin>>n>>m; |
| |
| if(n!=0&&m!=0) step(0,0); |
| |
| cout<<ans<<endl; |
| |
| return 0; |
| |
| } |
-
利用递归,将大问题拆分为同类型的小问题解决
-
一般情况下,从初识状态出发,进行扩展得到若干新的状态
-
选定一个状态继续深入,直到不再出现新的状态为止,然后回退,并将上一层的状态恢复
-
重复上述过程,直到将所有可以达到的状态全部遍历
-
一般来说,使用DFS
在提前搜索到答案时一般只进行标记,不提前返回或退出
-
当搜索过程中出现明显不满足目标的状态时可以提前返回,减少搜索次数
原题链接
描述
小明现在在玩一个游戏,游戏来到了教学关卡,迷宫是一个N*M的矩阵。
小明的起点在地图中用“S”来表示,终点用“E”来表示,障碍物用“#”来表示,空地用“.”来表示。
障碍物不能通过。小明如果现在在点(x,y)处,那么下一步只能走到相邻的四个格子中的某一个:(x+1,y),(x-1,y),(x,y+1),(x,y-1);
小明想要知道,现在他能否从起点走到终点。
输入格式:
本题包含多组数据。
每组数据先输入两个数字N,M
接下来N行,每行M个字符,表示地图的状态。
数据范围:
2<=N,M<=500
保证有一个起点S,同时保证有一个终点E.
输出格式:
每组数据输出一行,如果小明能够从起点走到终点,那么输出Yes,否则输出No
输入样例:
输出样例
分析
- 走出迷宫需要对每一个点进行搜索
- 首先需要记录
S
的坐标
- 从
S
开始搜索,需要偏移量数组
- 对于
DFS
在搜索时,若搜到E
点则标记答案
DFS代码
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| const int N=510; |
| |
| int n,m; |
| |
| char mp[N][N]; |
| |
| bool vis[N][N]; |
| |
| int s1,s2; |
| |
| int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; |
| |
| bool flag; |
| |
| void dfs(int x,int y){ |
| |
| if(mp[x][y]=='E'){ |
| flag=1; |
| } |
| |
| for(int i=0;i<4;i++){ |
| |
| int l=x+dx[i],r=y+dy[i]; |
| if(l>=1&&l<=n&&r>=1&&r<=m&&!vis[l][r]&&mp[l][r]!='#'){ |
| vis[l][r]=1; |
| dfs(l,r); |
| } |
| |
| } |
| |
| } |
| |
| int main(){ |
| |
| while(cin>>n>>m){ |
| |
| |
| flag=0; |
| memset(vis,0,sizeof vis); |
| memset(mp,0,sizeof mp); |
| |
| for(int i=1;i<=n;i++){ |
| for(int j=1;j<=m;j++){ |
| cin>>mp[i][j]; |
| if(mp[i][j]=='S'){ |
| s1=i; |
| s2=j; |
| } |
| } |
| } |
| |
| dfs(s1,s2); |
| |
| if(flag) cout<<"Yes"<<endl; |
| else cout<<"No"<<endl; |
| |
| } |
| |
| return 0; |
| |
| } |
原题链接
描述
给定一个整数 n,将数字 1∼n 排成一排,将会有很多种排列方法。
现在,请你按照字典序将所有的排列方法输出。
输入格式
共一行,包含一个整数 n。
输出格式
按字典序输出所有排列方案,每个方案占一行。
数据范围
输入样例:
输出样例:
| 1 2 3 |
| 1 3 2 |
| 2 1 3 |
| 2 3 1 |
| 3 1 2 |
| 3 2 1 |
分析:
代码
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| const int N=1e6+3; |
| |
| int ans[N]; |
| |
| int a[N]; |
| |
| bool vis[N]; |
| |
| int n; |
| |
| void dfs(int u){ |
| |
| if(u==n){ |
| |
| for(int i=0;i<n;i++){ |
| cout<<ans[i]<<" "; |
| } |
| cout<<endl; |
| return ; |
| |
| } |
| |
| for(int i=0;i<n;i++){ |
| if(!vis[a[i]]){ |
| vis[a[i]]=1; |
| ans[u]=a[i]; |
| dfs(u+1); |
| vis[a[i]]=0; |
| } |
| } |
| |
| } |
| |
| int main(){ |
| |
| cin>>n; |
| |
| for(int i=0;i<n;i++){ |
| a[i]=i+1; |
| } |
| |
| dfs(0); |
| |
| return 0; |
| |
| } |
扩展:
- 利用
STL
中的next_permutation
函数
next_permutation
按照字典序生成下一个排列组合
复杂度O(n)
排列范围[first,last)
代码:
| #include <bits/stdc++.h> |
| using namespace std; |
| int main(){ |
| int n,a[1000]; |
| cin>>n; |
| for(int i=1;i<=n;i++){ |
| a[i]=i; |
| } |
| do{ |
| for(int i=1;i<=n;i++){ |
| cout<<a[i]<<" "; |
| } |
| cout<<endl; |
| }while(next_permutation(a+1,a+n+1)); |
| return 0; |
| } |
原题链接
描述
给出一个 nn×n的国际象棋棋盘,你需要在棋盘中摆放nn个皇后,使得任意两个皇后之间不能互相攻击。具体来说,不能存在两个皇后位于同一行、同一列,或者同一对角线。请问共有多少种摆放方式满足条件。
输入描述:
一行,一个整数n(1≤n≤12),表示棋盘的大小。
输出描述:
输出一行一个整数,表示总共有多少种摆放皇后的方案,使得它们两两不能互相攻击。
样例输入
样例输出
分析
- 由于皇后不能互相攻击到,故棋盘的每一行,每一列及其有皇后存在的对角线的平行线上有且只有一个皇后
- 递归处理,每一次递视为一次对棋子的判断,递归的层数视为棋盘的层数,每一层选择放置一个皇后
- 对于递归的每一层,遍历这层棋盘的格子,判断以该格子的列和对角线的平行线上是否存在过皇后
- 若放置皇后,则需要对放置的格子所在的列和对角线的平行线进行标记
- 递归处理上述过程,直到将皇后放置完毕
- 对于对角线的处理,我们 可以利用数学关系,转换为截距进行标记
k = i + u
或k = i - u
代码
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| const int N=510; |
| |
| bool y[N],l[N],r[N]; |
| |
| int n; |
| |
| int ans; |
| |
| void dfs(int u){ |
| |
| if(u==n){ |
| ans++; |
| return ; |
| } |
| |
| for(int i=0;i<n;i++){ |
| |
| if(!y[i]&&!l[u+i+n]&&!r[u-i+n]){ |
| y[i]=l[u+i+n]=r[u-i+n]=1; |
| dfs(u+1); |
| y[i]=l[u+i+n]=r[u-i+n]=0; |
| } |
| |
| } |
| |
| } |
| |
| int main(){ |
| |
| cin>>n; |
| |
| dfs(0); |
| |
| cout<<ans<<endl; |
| |
| } |
原题链接
题解
原题链接
题解
原题链接
题解
原题链接
题解
原题链接
题解
评论