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

wordpress问答社区主题无锡网站建设优化

wordpress问答社区主题,无锡网站建设优化,上海白标seo,怎么做html5网站dfs 回溯 剪枝 这个题和dfs有关#xff0c;但是我之前没有接触过#xff0c;我看了这一篇很好的文章#xff0c;看完之后写的答案。 我觉得很好的总结#xff1a; dfs模板 int check(参数) {if(满足条件)return 1;return 0; }void dfs(int step) {判断边界{相应操作}尝试…dfs 回溯 剪枝 这个题和dfs有关但是我之前没有接触过我看了这一篇很好的文章看完之后写的答案。 我觉得很好的总结 dfs模板 int check(参数) {if(满足条件)return 1;return 0; }void dfs(int step) {判断边界{相应操作}尝试每一种可能{满足check条件标记继续下一步dfs(step1)恢复初始状态回溯的时候要用到} } 尝试每一种可能一般都是用for循环。 在一些情况下for循环这一步可以写到外面去然后再调用dfs比如这题就可以。  题目 我的思路 其实就是模仿我刚刚提到的文章。 我的dfs是bool dfs(std::vectorstd::vectorchar grid, std::string target, int step, int pre_i, int pre_j) 是拿上一步的pre_i和pre_j作为输入然后我发现这样写没办法启动dfs但是我当时脑子抽了没找到直接输入i和j就能做出来的办法。所以只能第一步遍历所有格子的时候把它写在dfs外面总之有点愚蠢。但是执行时间和内存都比我下一种写法要少很多这是为啥 我自己写的 复杂度 代码 #include vector #include string #include iostream //我写的 dfs 剪枝 回溯 class Solution { public:Solution(){}bool wordPuzzle(std::vectorstd::vectorchar grid, std::string target) {n target.size();if (n 0 || grid.empty() || grid[0].empty())return false;rows grid.size();//行cols grid[0].size();//列int step 1;vis std::vectorint(rows * cols);res std::vectorchar(n);for (int i 0; i rows; i)//因为我写的dfs需要接受前一个dfs的位置i,j为了启动只能把第一轮遍历写在外面了{for (int j 0; j cols; j){if (grid[i][j] target[step - 1]){res[step - 1] grid[i][j];//访问vis[i * cols j] 1;//标记result dfs(grid, target, step 1, i, j);if (result)return result;vis[i * cols j] 0;//回溯res[step - 1] \0;//回溯}}}return result;} private:bool dfs(std::vectorstd::vectorchar grid, std::string target, int step, int pre_i, int pre_j){if (step n 1)return true;//中止条件 判断边界for (int i 0; i rows; i)//尝试每一种可能{for (int j 0; j cols; j){if (vis[i * cols j] 0 //走过的不要grid[i][j] target[step-1]//不相同的直接不要((i * cols j) (pre_i * cols pre_j - cols) ||//上(i * cols j) (pre_i * cols pre_j cols) ||//下(i pre_i j pre_j - 1) ||//左(i pre_i j pre_j 1)))//右{res[step-1] grid[i][j];//访问vis[i * cols j] 1;//标记result dfs(grid, target, step 1, i, j);//下一个if (result)return result;vis[i * cols j] 0;//回溯res[step - 1] \0;//回溯}}}return result;}int n 0;int rows 0;int cols 0;std::vectorint vis;std::vectorchar res;bool result false; };void Test_solution1() {Solution solution;std::vectorstd::vectorchar grid{ { C,A,A} ,{A,A,A},{B,C,D} };std::cout solution.wordPuzzle(grid ,std::string(AAB));} 答案思路 把循环写到dfs外面了。 dfs判断的是当前的点。所以dfs是 dfs(std::vectorstd::vectorchar grid, std::string target, int step, int i, int j) 这里传进来的i和j是需要被判断的点而不是我写的pre_i和pre_j 找方向用的是 result dfs(grid, target, step 1, i - 1, j) ||                 dfs(grid, target, step 1, i 1, j) ||                 dfs(grid, target, step 1, i, j - 1) ||                 dfs(grid, target, step 1, i, j 1); 比我的好多了呵呵。 但是测试的时间和内存异常多。然后我又测试了答案提供的还是很多时间和内存很奇怪啊。 看了答案之后自己根据思路重新写了一遍代码 #include vector #include string #include iostream //看了答案之后模仿写的 dfs 剪枝 回溯 //这个要用很多内存 呃为什么 class Solution { public:Solution() {}bool wordPuzzle(std::vectorstd::vectorchar grid, std::string target) {n target.size();if (n 0 || grid.empty() || grid[0].empty())return false;rows grid.size();//行cols grid[0].size();//列int step 1;vis std::vectorint(rows * cols);//res std::vectorchar(n);for (int i 0; i rows; i)//循环写在外面了{for (int j 0; j cols; j){result dfs(grid, target, step, i, j);if (result)return result;}}return result;} private:bool dfs(std::vectorstd::vectorchar grid, std::string target, int step, int i, int j){if (step n 1)return true;//中止条件if (i 0 i rows j 0 j cols //超过的不要vis[i * cols j] 0 //走过的不要grid[i][j] target[step - 1])//不相同的直接不要{//res[step - 1] grid[i][j];//访问vis[i * cols j] 1;//标记result dfs(grid, target, step 1, i - 1, j) ||dfs(grid, target, step 1, i 1, j) ||dfs(grid, target, step 1, i, j - 1) ||dfs(grid, target, step 1, i, j 1);if (result)return result;vis[i * cols j] 0;//res[step - 1] \0;}return result;}int n 0;int rows 0;int cols 0;std::vectorint vis;//std::vectorchar res;bool result false; };void Test_solution2() {Solution solution;std::vectorstd::vectorchar grid{ { C,A,A} ,{A,A,A},{B,C,D} };std::cout solution.wordPuzzle(grid, std::string(AAB));} 测试结果
http://wiki.neutronadmin.com/news/446384/

相关文章:

  • 展示网站欣赏淄博市沂源县城乡建设局网站
  • 电商建设网站资源丰富免费的网站推荐排名
  • 叫什么公子的网站做ppt的重庆九龙坡区网站建设
  • 上海企业免费网站建设淘宝详情页模板
  • 网站后台英文网站下载软件入口
  • 如何查到网站是谁做的app开发公司推荐
  • 潍坊网站建设app北京企业模板建站有哪些
  • 站长统计代码做云教育集群网站
  • 柏乡企业做网站中国开头的网站怎么做
  • 软件开发工程师报考条件沧州百度seo
  • 网站备案要多长时间河南商务学校网站建设
  • 化工厂建设网站天津建设教育培训中心
  • 网站策划书的内容北京软件开发培训
  • seo搜索优化 指数怎么优化网站排名具体怎么做
  • ps做网站页面先后顺序空间 网站
  • 中国黄页免费版网站关键词优化快速排名
  • 网站建设要架服务器网络营销中网站建设的策略
  • 淘客网站做单品类淮南建设局网站备案
  • 网站建设与管理是干嘛的可以做高清思维导图的网站
  • 网站公司做的网站有最字网站设计制作公司需要什么资质
  • 沈阳专业制作网站网站子站怎么做、
  • 建设销售型网站免费个人网站搭建
  • 网站建设 广州网站建设专业公司佛山网站代运营准度科技有限公司
  • 网站 位置导航青岛网站建设运营推广
  • 开源网站推广9块9 wordpress
  • 上海做网站 公司app网站排名
  • 网站源码检测浙江建设特种证书查询
  • 汕头网站建设推荐游戏分销代理平台
  • 网站开发有哪些语言手机网站大全下载
  • 自适应网站模版深圳网站建设制作设计企业