POJ 1321 棋盘问题

题目在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;
}

评论

4 楼 fuliang 2009-08-02  

gedoua 写道

嗯 以前我一直是那么写代码的，就是输入一个测试一个，这回就不行了。。。我朋友说让我试试一下把所有的测试全输入试试，我的代码就运行错误了。nextChar()String包里没有这个方法吧。还有别的方法读字符吗？我的方法好麻烦。我是个初学者，不好意思打扰您拉。

nextChar()是Scanner的方法，不是String里边的

3 楼 gedoua 2009-08-02  

嗯 以前我一直是那么写代码的，就是输入一个测试一个，这回就不行了。。。我朋友说让我试试一下把所有的测试全输入试试，我的代码就运行错误了。nextChar()String包里没有这个方法吧。还有别的方法读字符吗？我的方法好麻烦。我是个初学者，不好意思打扰您拉。

2 楼 fuliang 2009-08-02  

gedoua 写道

java不行是因为把测试数据一下全部输入会出现错误。。。我也遇到这个问题了，但是不知道怎么输入才对，您能帮我写一下吗？就写输入部分就行，谢谢了，我的很多poj题都是java写的，算法都对，就是这个输入，头疼！！！希望您能给我解答谢谢了

为什么一次把所有的测试数据读入呢？
acm的题目都是每次读入一个测试数据 然后输出结果的，而不是读入所有的测试数据，然后再依次的输出结果的。
像这个题目用java读入就可以改成：

Scanner sc = new Scanner(System.in);
while(true){
  n = sc.nextInt();
  k = sc.nextInt();
  if(k == -1)
    break;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
       borad[i][j] = sc.nextChar();
    }
    sc.nextChar();//滤过换行
  }
  //..
}

1 楼 gedoua 2009-08-02  

java不行是因为把测试数据一下全部输入会出现错误。。。我也遇到这个问题了，但是不知道怎么输入才对，您能帮我写一下吗？就写输入部分就行，谢谢了，我的很多poj题都是java写的，算法都对，就是这个输入，头疼！！！希望您能给我解答谢谢了