南通网站建设规划书,微博推广渠道,wordpress建站方向,企业互联网营销推广方案目录 算法简介#xff1a;
枚举方式#xff1a;
1.每一个数都有两种状态#xff0c;也就是选或不选#xff0c;时间复杂度也就是2^n#xff0c;每一个数都有选和不选两种状态。 2.生成给定集合所有可能排列的方法#xff0c;与之不同的是同样是1 2 3三个数字#xff0…
目录 算法简介
枚举方式
1.每一个数都有两种状态也就是选或不选时间复杂度也就是2^n每一个数都有选和不选两种状态。 2.生成给定集合所有可能排列的方法与之不同的是同样是1 2 3三个数字12 3和 132是两种方案。
3.不考虑元素的顺序。也就是 1 2 3 和 1 3 2是同一种方案
图的搜索 奶牛和草丛
题目描述
输入
输出
样例输入
样例输出
解题步骤
解题代码
练习
洛谷P1219 [USACO1.5] 八皇后 Checker Challenge
题目描述
输入格式
输出格式
留下你的足迹吧谢谢。 算法简介
DFS算法的基本思想是从图中的某个顶点v出发访问此顶点然后依次从v的未被访问的邻接点出发深度优先遍历图直至图中所有和v有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问则另选图中一个未曾被访问的顶点作起始点重复上述过程整个进程反复进行直到所有顶点都被访问为止。 枚举方式
1.每一个数都有两种状态也就是选或不选时间复杂度也就是2^n每一个数都有选和不选两种状态。 代码实现
#includebits/stdc.h
using namespace std;
int n;
int vis[20];
void dfs(int x){if(xn){for(int i1;in;i){if(vis[i]1)couti ;}cout\n;return;}vis[x]-1;dfs(x1);vis[x]0;vis[x]1;dfs(x1);vis[x]0;
}
int main(){cinn;dfs(1);return 0;
} 2.生成给定集合所有可能排列的方法与之不同的是同样是1 2 3三个数字12 3和 132是两种方案。 代码实现 for(int i1;in;i){if(!vis[i]){vis[i]1;//选过标记a[x]i;//表示被选dfs(x1);//继续选下一个vis[i]0;//回溯重置a[x]0;}}
3.不考虑元素的顺序。也就是 1 2 3 和 1 3 2是同一种方案 代码实现 for(int iu;in;i){a[x]i;dfs(x1,i1);//选下一个数字从i1开始往后选a[x]0;}
图的搜索
以下题举例 奶牛和草丛 题目描述
奶牛Bessie计划好好享受柔软的春季新草。新草分布在R行C列的牧场里。它想计算一下牧场中的草丛数量。 在牧场地图中每个草丛要么是单个“#”要么是有公共边的相邻多个“#”。给定牧场地图计算有多少个草丛。 例如考虑如下5行6列的牧场地图 .#.... ..#... ..#..# ....## .....# 这个牧场有3个草丛一个在第一行一个在第二列横跨了二、三行一个在第三行横跨了三、四、五行。
输入
第一行包含两个整数R和C中间用单个空格隔开。 接下来R行每行C个字符描述牧场地图。字符只有“#”或“.”两种。(1 R, C 100 )
输出
输出一个整数表示草丛数。
样例输入
5 6
.#....
..#...
..#..#
....##
.....#
样例输出
3
这是一题典型的dfs
解题步骤 1.选择起始点从图的某个顶点u开始。 2.标记当前顶点将当前顶点u标记为已访问以避免重复访问。 3.遍历邻接点对于u的每个未访问的邻接点v递归地执行dfs从v开始。 4.回溯当没有更多的邻接点可以遍历时返回到上一步的顶点。
解题代码
#includebits/stdc.h
using namespace std;
int m,n,c;
char a[105][105];
int b[105][105];
void f(int x,int y){if(x1xmy1yn){if(a[x][y]#b[x][y]0){//是草丛且没被遍历b[x][y]1;//搜四个方向f(x1,y);f(x-1,y);f(x,y1);f(x,y-1);}}else return;//不符条件回溯。
}
int main(){cinmn;//输入for(int i1;im;i){for(int j1;jn;j){cina[i][j];}}//遍历查找for(int i1;im;i){for(int j1;jn;j){if(a[i][j]#b[i][j]0){c;f(i,j);}}}coutc;return 0;
}
练习
洛谷P1219 [USACO1.5] 八皇后 Checker Challenge
题目描述
一个如下的 6×66×6 的跳棋棋盘有六个棋子被放置在棋盘上使得每行、每列有且只有一个每条对角线包括两条主对角线的所有平行线上至多有一个棋子。 上面的布局可以用序列 2 4 6 1 3 5 来描述第 i 个数字表示在第 i 行的相应位置有一个棋子如下
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。 并把它们以上面的序列方法输出解按字典顺序排列。 请输出前 3 个解。最后一行是解的总个数。
输入格式
一行一个正整数 n表示棋盘是 n×n 大小的。
输出格式
前三行为前三个解每个解的两个数字之间用一个空格隔开。第四行只有一个数字表示解的总数。
#includebits/stdc.h
using namespace std;
int n,vx[15],vy[15],v1[30],v2[30],a[15],c;
void f(int i){if(in){c;if(c3){for(int k1;kn;k)couta[k] ;coutendl;}return;}for(int j1;jn;j){if(!vx[i]!vy[j]!v1[i-jn]!v2[ij]){a[i]j;vx[i]1;vy[j]1;v1[i-jn]1;v2[ij]1;f(i1);vx[i]0;vy[j]0;v1[i-jn]0;v2[ij]0;}}
}
int main() {cinn;f(1);coutc;return 0;
}
留下你的足迹吧谢谢。
