uvaoj 639 - Don't Get Rooked 和8皇后不同的地方：每行可以放多个。之前觉得递归cur+1的方法是不行的，因为有些行可能一个都不能放象棋。另外，在做冲突检测的时候，只做前向考虑，即只判断该位置之前是否会冲突。 dfs中有两个for循环，把每行能放的棋子先尽可能放完，然后再考虑下一行。注意和8皇后问题的区别。

gistfile1.cpp

#include <iostream>
#include <cstring>
#include <fstream>
#define N 4
using namespace std;

int board[N][N];
int total;
int maxm;

void searchres(int n,int cur){
    int i,j;
    //cout<<"cur = "<<cur<<endl;
    for(i = cur; i < n; i++){
        for(j = 0; j < n; j++) if(board[i][j] == 0){
            int row = 1, column = 1;
        //-------------------以下是判断是否可以放在board[cur][j]上-------------------
            for(int k = j; k >= 0; k--)
                if(board[i][k] == 2)break;
                else if(board[i][k] == 1) row = 0;
            for(int k = i; k >= 0; k--)
                if(board[k][j] == 2)break;
                else if(board[k][j] == 1) column = 0;
        //------------------------------------------------------------------------------
            if(row && column){//如果行列上都没有1，则表明该位置可以放。
                board[i][j] = 1;
                total++;
                //searchres(n,cur+1);//这是错误的
                searchres(n,i);//要先把这一行能放的给放满了，所以继续对i递归。
                //total--;
                board[i][j] = 0;
            }
        }
    }
    if(i == n && j == n){
        if(total > maxm) maxm = total;
        total = 0;
        return;
    }
}

int main(){
    int n;
    char c;
    while(cin>>n){
            if(n == 0)break;
            memset(board,0,sizeof(board));
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    cin>>c;
                    if(c == 'X')board[i][j] = 2;//有‘X’的地方用2表示，
                    else board[i][j] = 0;//有‘.’的地方用0表示。
                }
            }
            maxm = 0;
            total = 0;
            searchres(n,0);
            cout<<maxm<<endl;
    }
    return 0;
}

下面是错误的代码，逻辑就是错误的：
#include <iostream>
#include <cstring>
#include <fstream>
#define N 4
using namespace std;

int board[N][N];
int total;
int maxm;


void searchres(int n,int cur){
    int j;
    if(cur == n){
        if(total >  maxm) maxm = total;
        return;
    }
    else for(j = 0; j < n; j++) if(board[cur][j] == 0){
        int row = 1, column = 1;
        cout<<"row = "<<cur<<" column = "<<j<<endl;
        //-------------------以下是判断是否可以放在board[cur][j]上-------------------
        for(int k = j; k < n; k++)
            if(board[cur][k] == 2)break;
            else if(board[cur][k] == 1) row = 0;
        for(int k = j; k >= 0; k--)
            if(board[cur][k] == 2)break;
            else if(board[cur][k] == 1) row = 0;
        for(int k = cur; k < n; k++)
            if(board[k][j] == 2)break;
            else if(board[k][j] == 1) column = 0;
        for(int k = cur; k >= 0; k--)
            if(board[k][j] == 2)break;
            else if(board[k][j] == 1) column = 0;
        //------------------------------------------------------------------------------
        if(row && column){//如果行列上都没有1，则表明该位置可以放。
            board[cur][j] = 1;
            total++;
            searchres(n,cur+1);
            total--;
            board[cur][j] = 0;
        }
    }
}
int main(){
    ifstream fin;
    fin.open("D:\\C++\\test\\bin\\Debug\\123");
    int n;
    char c;
    while(fin>>n){
            if(n == 0)break;
            memset(board,0,sizeof(board));
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    fin>>c;
                    if(c == 'X')board[i][j] = 2;//有‘X’的地方用2表示，
                    else board[i][j] = 0;//有‘.’的地方用0表示。
                }
            }
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++)
                    cout<<board[i][j]<<" ";
                cout<<endl;
            }
            maxm = 0;
            total = 0;
            searchres(n,0);
            cout<<maxm<<endl;
    }
    return 0;
}