首页 > 代码库 > poj 1321 棋盘问题 【DFS】
poj 1321 棋盘问题 【DFS】
题意:。。。
策略:深搜.
仔细分析我们发现,我们只需要对列进行标记,对于行我们考虑放棋子还是不放就行了。
代码:
#include<stdio.h> #include<string.h> char s[10][10]; int n, m; int vis[10]; int ans; void dfs(int cur, int step) { if(step == m){ ans ++; return; } if(cur > n-1) return ; int i, j; for(i = cur; i < n; i ++){ for(j = 0; j < n; j ++){ if(s[i][j] == '#'&&!vis[j]){ vis[j] = 1; dfs(i+1, step+1);//向下一行放置 vis[j] = 0; } } } } int main() { int i, j; while(scanf("%d%d", &n, &m), n!=-1&&m!=-1){ for(i = 0; i < n; i ++){ scanf("%s", s[i]); } memset(vis, 0, sizeof(vis)); ans = 0; dfs(0, 0); printf("%d\n", ans); } return 0; }题目链接:点击打开链接
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。