题目在http://acm.pku.edu.cn/JudgeOnline/problem?id=1321
steve同学用java写了这道题老是runtime error,我让他把数组开大点,说结果还是runtime error,于是我写了一下,结果ac了,后来他用c++写也ac了。
这个题就是回溯法,和八皇后类似。
/**
*Author fuliang
*poj 1321
*/
#include<iostream>
#include<cstring>
using namespace std;
const int MAX = 9;
char board[MAX][MAX];//记录棋盘状态
bool placed_c[MAX];//记录一列是否已经放过棋子
int count;//放棋子的方案数
int num_p;//已放棋子数目
int n,k;//棋盘n*n,放的棋子数k
/*
*是否可以放棋子
*/
bool can_place(int i,int j){
return !placed_c[j] && board[i][j] == '#';
}
/*
*深搜/回溯
*/
void DFS(int i){
if(num_p == k){
count++;
return;
}
if(i >= n)
return;
int j;
for(j = 0; j < n; j++){
if(can_place(i,j)){
placed_c[j] = true;
num_p++;
DFS(i+1);
placed_c[j] = false;
num_p--;
}
}
DFS(i+1);//i行不放棋子
}
int main(){
int i,j;
while(cin >> n >> k, k != -1){
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
cin >> board[i][j];
count = 0;
num_p = 0;
memset(placed_c,false,sizeof(placed_c));
DFS(0);
cout << count << endl;
}
return 0;
}
分享到:
相关推荐
POJ1321棋盘问题 很好两种解法很值得去参考一下 完整的实验报告还有代码希望kan
北大POJ1321-Chess Problem POJ1321-Chess Problem
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
放炮问题,北大网站 POJ 1185 算法
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
POJ1048,加强版的约瑟夫问题 难度中等
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ1004-Financial Management 解题报告+AC代码
北大poj1012-Joseph【经典约瑟夫问题】 poj1012-Joseph【经典约瑟夫问题】
poj.grids.cn题型汇总 ...棋盘分割 日程安排问题 最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等) 方块消除游戏(某区间可以连续消去求最大效益) 资源分配问题 数字三角形问题 漂亮的打印
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
POJ 1328 java做!雷达问题!java版本!AC答案~
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
百练POJ1088滑雪问题的源代码,C写的,不过后缀是.cpp。写的还算比较易懂,呵呵