首页 > 代码库 > poj 2837 Silver Matrix 不使用栈的深搜
poj 2837 Silver Matrix 不使用栈的深搜
题意:
给定k,让构造一个2^k*2^k的矩阵,使得对任意i,第i行和第i列由1,2,...2^k-1这2^k-1个数组成。
分析:
很明显是个深搜题。设n=2^k,则搜素树高度(状态空间维度)为n,每个状态可扩展n个状态,复杂度n^n,大概是512^512。。。所以必须有强力的剪枝而且不要用递归去写。一般对深搜来说,搜索树高度固定的话可以用for循环直接枚举,不固定话要用递归或栈,这题搜索树高度不固定(n为输入),怎么办呢?。。这样可以清楚明了地搞定:dfs的while循环写法。
代码:
//poj 2837 //sep9 #include <iostream> using namespace std; const int maxN=520; int a[maxN][maxN]; bool used[2][maxN][2*maxN]; int n; void solve() { int x,y,i; x=y=1; a[x][y]=0; while(x<=n){ int ok=0; for(i=a[x][y]+1;i<2*n;++i) if(!used[0][x][i]&&!used[1][x][i]&&!used[0][y][i]&&!used[1][y][i]){ a[x][y]=i; used[0][x][i]=used[1][x][i]=used[0][y][i]=used[1][y][i]=true; ++y; if(y>n){y=1,++x;} a[x][y]=0; ok=1; break; } if(ok==0){ --y; if(y==0){y=0,--x;} i=a[x][y]; used[0][x][i]=used[1][x][i]=used[0][y][i]=used[1][y][i]=false; } } } int main() { scanf("%d",&n); n=(1<<n); memset(used,false,sizeof(used)); solve(); for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j) printf("%d ",a[i][j]); printf("\n"); } return 0; }
poj 2837 Silver Matrix 不使用栈的深搜
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。