当前位置: 首页 > news >正文

网络创作网站html网页制作个人主页制作教程

网络创作网站,html网页制作个人主页制作教程,织梦网站栏目设计,百度视频免费下载深度优先搜索#xff08;DFS#xff09; 求连通块 #x1f449;HDOJ-1241 Oil Deposits 【题目】石油勘探公司把油田分成许多的大格#xff0c;每个大格又分为许多小格#xff0c;然后分析各个小格是否有石油矿藏。有矿藏的小格#xff08;用表示#xff09;称为容器.…深度优先搜索DFS 求连通块 HDOJ-1241 Oil Deposits 【题目】石油勘探公司把油田分成许多的大格每个大格又分为许多小格然后分析各个小格是否有石油矿藏。有矿藏的小格用表示称为容器. 如果2个容器相连横、竖、斜, 则它们是同一矿区的不同部分。输入各大格的矿藏分布无矿藏用*表示输出其中有多少个不同的矿区。 #includeiostream using namespace std; char g[105][105]{0}; int m,n; int dir[8][2]{{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}; void dfs(int x,int y){if(x0||xm||y0||yn||g[x][y]*) return;//越界或走过则返回g[x][y]*;//标记走过for(int k0;k8;k)//查找下一级可用点dfs(xdir[k][0],ydir[k][1]); } int main(){ while(cinmnm){//m行n列int i,j;for(i0;im;i)//建议从0开始便于整行输入cing[i];int num0;for(i0;im;i)for(j0;jn;j)if(g[i][j])//仅在第一级递归计数故分离{num;dfs(i,j);}coutnumendl;}return 0; }HDOJ-1031 N皇后问题 【题目】在N×N的方格棋盘放置了N个皇后使得它们不相互攻击即任意2个皇后不允许处在同一排同一列也不允许处在与棋盘边框成45角的斜线上。输入给定的NN≤10输出有多少种合法的放置方法。 【思路】在N×N棋盘中摆N个皇后意味着每行有一个皇后每列有一个皇后每条主对角线有一个皇后每条副对角线有一个皇后换言之每个皇后控制着一行、一列。一条主对角线、一条副对角线。因此以每行对应一次循环用a,b,c三个数组存储各主对角线、副对角线、列的占用情况。点(x,y)位于第x行第y列第y-xn条主对角线(1-ny-xn-1处理使数组从1开始)第xy条副对角线(2xy2n)。 #includeiostream #includecstring using namespace std; int n,so; bool a[25],b[15],c[25];//a代表主对角线b代表列c代表副对角线 void dfs(int i){if(in) {so;return;}for(int j1;jn;j){//每列if(a[j-in]||b[j]||c[ij]) continue;//不可用则跳过a[j-in]true;b[j]true;c[ij]true;//标记控制区域dfs(i1);//查找下一行可用点a[j-in]false;b[j]false;c[ij]false;//取消标记} } int main(){int ans[15]{0};for(n1;n10;n){memset(a,false,sizeof(a));memset(b,false,sizeof(b));memset(c,false,sizeof(c)); so0;dfs(1);ans[n]so;}while(cinnn)coutans[n]endl;return 0; }HDOJ-1426 Sudoku Killer 【题目】输入一批不完整的数独地图未知数值用?表示输出它们的解。对于每组测试数据保证它有且只有一个解 【思路】 仔细分析发现与上一题有类似之处小格中的每一个数字x都可以看做是所在行、列、九宫格的数字x的控制数字——这个数字控制着所在行、列、九宫格在其控制区域内不能出现另一个x。用结构体存储空格的位置i0~8代表小格行标j0~8代表小格列标则i/3代表九宫格行标j/3代表九宫格列标。以每个空格对应一层递归用a,b,c三个数组存储各行、列、九宫格的可用性数组最后一维代表9个可能的数字其他维度代表序号。 由题意每个空格的值不全为9。当从最后一个空格已填写出发进行下一层递归时触发条件空格溢出记录填写完成函数返回到倒数第二个空格的下一次循环。填写完成条件满足循环变量的上一个值填写到真正的数独空格中函数再返回到倒数第三个空格……对于值为9的情况在循环之外另行处理。 用两层循环读入数独地图存到字符数组中读入的字符若是数字标记控制区域若是空格记录其位置坐标。 #includeiostream #includecstring #includecstdio using namespace std; char map[9][9]; struct space{int i;int j;}s[81]; bool a[9][12],b[9][12],c[3][3][12];//a代表行b代表列c代表九宫格 int sn,snm;//snSpace Number空格编号,snm空格编号最大值 int done;//done为1代表所有空格填写完成 void dfs(int sn){if(snsnm) {done1;return;}int v;for(v1;v9;v){//每个可能值if(done1) {map[s[sn].i][s[sn].j]0v-1;break;}if(a[s[sn].i][v]||b[s[sn].j][v]||c[s[sn].i/3][s[sn].j/3][v]) continue;//不可用则跳过a[s[sn].i][v]true;b[s[sn].j][v]true;c[s[sn].i/3][s[sn].j/3][v]true;//标记控制区域dfs(sn1);//填写下一个空格a[s[sn].i][v]false;b[s[sn].j][v]false;c[s[sn].i/3][s[sn].j/3][v]false;//取消标记}if(v10done1) map[s[sn].i][s[sn].j]0v-1; } int main(){char ch;int f1;do{int i,j;memset(a,false,sizeof(a));memset(b,false,sizeof(b));memset(c,false,sizeof(c));done0;sn0;for(i0;i9;i){for(j0;j9;j){cinch;if(ch!?) {a[i][ch-0]true;b[j][ch-0]true;c[i/3][j/3][ch-0]true;}else {s[sn].ii;s[sn].jj;sn;}map[i][j]ch;}}snmsn-1;dfs(0);if(f0) coutendl; else f0;//第二组数据开始输出前加一空行for(i0;i9;i){for(j0;j8;j)coutmap[i][j] ;coutmap[i][j]endl; } }while(scanf(%c,ch)!EOF);return 0; }【总结】1031 之前以单个方格作为区域可用性的存储单元这样一个方格可能被多个皇后控制故不能用bool标记而是放上一个皇后将其占用区域与控制区域值加1取消标记时将皇后将其占用区域与控制区域值减1。在处理射线扩展时方向数组与越界判断繁复放弃。参考他人之后发现利用棋盘长宽等长的条件可以简化问题。 记忆化搜索 【题目】 ○题目描述 在一个数阵中求出最长的严格下降路径的长度只能向相邻的上下左右走 如在下面这个数阵中最长的路径为25-24-23…-1(长度为25) 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 ○输入 第一行包含测试用例数T。每个测试用例第1行是名称字符串、行数r和列数c。之后是r行每行有c个数。N和r和c不大于100; ○输出 对于每个测试用例打印一行其中包含区域名称、冒号、空格和最长长度。 ○样例输入 1 scj 10 5 56 14 51 58 88 26 94 24 39 41 24 16 8 51 51 76 72 77 43 10 38 50 59 84 81 5 23 37 71 77 96 10 93 53 82 94 15 96 69 9 74 0 62 38 96 37 54 55 82 38 ○样例输出 scj: 7 【思路】 dp[i][j]存储从a[i][j]开始的最长路径长度则dp[i][j]1max(dp[x][y]) 点(x,y)与(i,j)相邻且不越界且满足a[i][j]a[x][y]若不存在这样的点max值为0 递推需要遵循线性顺序而本题涉及路径故使用记忆化搜索。记忆化搜索涉及递归原因是搜索过程中调用的结果可能尚未生成需要针对调用对象展开进一层搜索。 用一个函数来生成dp[i][j]的值函数执行过程中会更新从(i,j)出发的所有路径上的点的dp值但路径不一定包含所有点。在遍历所有点之后 a n s max ⁡ 1 ≤ i ≤ r , 1 ≤ j ≤ c d p [ i ] [ j ] ans\max_{1≤i≤r,1≤j≤c} dp[i][j] ans1≤i≤r,1≤j≤cmax​dp[i][j] #includequeue #includealgorithm #includeiostream #includecstdio #includecstring using namespace std; int r, c; int a[105][105]; int dp[105][105]; int search(int n, int m){int temp a[n][m];if(n - 1 0 a[n-1][m] temp) {if(dp[n-1][m] ! 0) dp[n][m] max(dp[n][m], dp[n-1][m] 1);else dp[n][m] max(dp[n][m], search(n-1, m) 1);}if(n 1 r a[n1][m] temp) {if(dp[n1][m] ! 0) dp[n][m] max(dp[n][m], dp[n1][m] 1);else dp[n][m] max(dp[n][m], search(n1, m) 1);}if(m - 1 0 a[n][m-1] temp) {if(dp[n][m-1] ! 0) dp[n][m] max(dp[n][m], dp[n][m-1] 1);else dp[n][m] max(dp[n][m], search(n, m-1) 1);}if(m 1 c a[n][m1] temp) {if(dp[n][m1] ! 0) dp[n][m] max(dp[n][m], dp[n][m1] 1);else dp[n][m] max(dp[n][m], search(n, m1) 1);}return dp[n][m]; }int main() {int t;scanf(%d, t);while(t--){memset(dp, 0, sizeof(dp));char ch[105];scanf(%s, ch);scanf(%d %d, r, c);for(int i 1; i r; i) for(int j 1; j c; j) scanf(%d, a[i][j]);int maxmum 0;for(int i 1; i r; i) for(int j 1; j c; j)maxmum max(maxmum, search(i, j));printf(%s: , ch);printf(%d\n, maxmum 1);}return 0; }
http://www.huolong8.cn/news/244301/

相关文章:

  • 烟台建设企业网站网站修改 iis6应用程序池
  • 先做网站先备案怎么获取wordpress的权限
  • 网站备案和服务器备案为什么要做网站推广
  • 重庆网站建设定制专业设计vi公司
  • 苏州做网站的哪个公司比较好建设部网站 注册违规
  • 哪个网站可以学做咸菜设计公司室内设计
  • 图片外链自己怎么优化网站排名
  • 华为建站丹东建设安全监督网站
  • 做电影网站违法企业软文
  • 网站代码 如何做层级关系推广平台免费
  • 昆明网站开发报价这周新闻热点事件
  • 网站开发文案阿里云做网站预装环境
  • 企业注册百家号可以做网站吗上海网站开发孵化
  • 吸引人的网站类型做企业网站用什么cms
  • dw做的网站如何上传企业官网的运营模式
  • 超市网站建设策划书凡科网建站入门教程
  • 宿迁网站制作云南网站设计哪家专业
  • 泸州网站建设哪家好阿里云怎么放多个网站
  • 小程序 手机网站重庆动画网站建设
  • 惠州网站建设企业建设谷歌公司网站费用
  • 免费建站的手机app找设计公司上哪个网站
  • 网站 医院信息化建设电梯配件做外贸在哪个网站
  • 温州微网站开发自己网站页面设计软件
  • 用英文介绍购物网站坪山做网站公司
  • 豫建设标 网站wordpress主题 资源站
  • 河南省 门户网站建设要求推广有什么好方法
  • 医疗网站建设临沂网站设计
  • 新手学做网站这本书外贸平台招聘
  • 网站建设以及推广销售客户怎么找建设微网站平台
  • 兰州市城市建设设计院公司网站seo优化的