首页 > 代码库 > HDU 1045 (DFS搜索)
HDU 1045 (DFS搜索)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1045
题目大意：在不是X的地方放O，所有O在没有隔板情况下不能对视（横行和数列），问最多可以放多少个O。
解题思路：
题目规模比较小（4*4），可以DFS解决。
对于一个点，要么放，要么不放。
放的话条件必须是上下左右四个方向扫到边界且不首先碰到X。
可以只对放的点进行标记，而对于不放的点不进行标记，这样当dep>n*n的时候及时return就行了。
注意每次dfs只需要按顺序考虑一个点，而不要同时对整个棋盘所有非X点同时dfs，否则就爆了。
原因是，每次只关联一个点，其它点都是不关联的，如果dfs等于做了大量重复计算。
#include "cstdio"#include "string"#include "cstring"#include "iostream"using namespace std;int n,vis[5][5],ans;char map[5][5];struct status{ int x,y; char type; status(int x,int y,char type):x(x),y(y),type(type) {} status() {}}P[20];bool judge(int X,int Y){ if(map[X][Y]==‘X‘) return false; for(int i=X-1; i>=1&&map[i][Y]!=‘X‘; i--) if(vis[i][Y]) return false; for(int i=X+1; i<=n&&map[i][Y]!=‘X‘; i++) if(vis[i][Y]) return false; for(int i=Y-1; i>=1&&map[X][i]!=‘X‘; i--) if(vis[X][i]) return false; for(int i=Y+1; i<=n&&map[X][i]!=‘X‘; i++) if(vis[X][i]) return false; return true;}void dfs(int p,int s){ if(p>n*n) {ans=max(ans,s);return;} dfs(p+1,s); vis[P[p].x][P[p].y]=true; if(judge(P[p].x,P[p].y)) dfs(p+1,s+1); vis[P[p].x][P[p].y]=false;}int main(){ //freopen("in.txt","r",stdin); ios::sync_with_stdio(false); string tt; while(cin>>n&&n) { memset(vis,0,sizeof(vis)); int cnt=0;ans=0; for(int i=1;i<=n;i++) { cin>>tt; for(int j=0;j<tt.size();j++) { P[++cnt]=status(i,j+1,tt[j]); map[i][j+1]=tt[j]; } } dfs(1,0); cout<<ans<<endl; }}
| 11909497 | 2014-10-19 11:59:35 | Accepted | 1045 | 0MS | 292K | 1335 B | C++ | Physcal |
HDU 1045 (DFS搜索)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。