【算法学习笔记】76.DFS 回溯检测 SJTU OJ 1229 mine
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【算法学习笔记】76.DFS 回溯检测 SJTU OJ 1229 mine,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1568字,纯文字阅读大概需要3分钟。
内容图文
扫雷玩得好还是有点好处的......
这个题一开始像从后向前按照第一排的数字进行DFS 发现自己真傻,先不说这种情况下每个数字的填写情况很多, 还要处理相邻位置的问题。
所以可以对每一位有没有地雷进行枚举。处理每一位的时候,要保证上一个数字是合理的,否则不用进行下去了,类似回溯,注意have变量的处理就好了。
#include <iostream> #include <stack> usingnamespace std; //最长 暗示dfs //遇到3 和 0 其实只有一种情况 //遇到2 和 1 有三种情况 //遇到* 有 2+2*3 = 8种情况, //可见如果以数字为dfs的条件的话 很麻烦 还不如直接用0 1 来枚举每个炸弹的位置 //其实如果数据小的话 可以直接遍历所有可能解 然后进行验证 但是因为n过大,全部情况根本没有办法枚举完,另外就是验证的效率很低 //所以还是dfsint n; string nums; bool isMine[100000+10]={false}; void init(){ cin>>n; cin>>nums; } bool have = false; int alreadyHave(int cur){ int res = 0; res += isMine[cur]; if(cur>0) res += isMine[cur-1]; if(cur<n-1) res += isMine[cur+1]; return res; } bool canPut(int cur){ if(nums[cur]==‘*‘) returntrue; elsereturn (‘0‘ + alreadyHave(cur) ) <= nums[cur]; } bool exactPut(int cur){ if(nums[cur]==‘*‘) returntrue; elsereturn (‘0‘ + alreadyHave(cur) ) == nums[cur]; } void dfs(int cur){ if(have) return; if(cur<0){ have = exactPut(0); return; } isMine[cur] = true; if((cur == n-1 and canPut(cur)) or (cur<n-1 and exactPut(cur+1)) ) dfs(cur-1); if(have)//不必继续return; isMine[cur] = false; if((cur == n-1 and canPut(cur)) or (cur<n-1 and exactPut(cur+1)) ) dfs(cur-1); return; } void build(){ dfs(n-1); int ans = 0; for (int i = 0; i < n; ++i) { if(isMine[i]) ans++; } cout<<ans<<endl; for (int i = 0; i < n; ++i) { cout<<isMine[i]; } cout<<endl; } int main(int argc, charconst *argv[]) { init(); build(); return0; }
原文:http://www.cnblogs.com/yuchenlin/p/sjtu_oj_1229.html
内容总结
以上是互联网集市为您收集整理的【算法学习笔记】76.DFS 回溯检测 SJTU OJ 1229 mine全部内容,希望文章能够帮你解决【算法学习笔记】76.DFS 回溯检测 SJTU OJ 1229 mine所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。