原始博客地址： http://www.fuxiang90.com/2012/07/usaco1-5-checker-challenge/拿到題目我的第一反應(yīng)是八皇后問(wèn)題，順利的寫(xiě)出了遞歸解法，弄完這個(gè)，感覺(jué)自己寫(xiě)遞歸和回溯有了一定的進(jìn)步了,至此第一章做完了，再接再厲。

但是提交后，在13 這個(gè)測(cè)試樣例超時(shí)，然后就在想怎么剪枝

• 之前在判斷放棋子是否沖突的時(shí)候，是在放的位置往四個(gè)方向拓展，如果沒(méi)有沖突就放 。現(xiàn)在改進(jìn)為直接判斷 和之前放置的棋子是否沖突。
• 對(duì)稱(chēng)剪枝，這個(gè)在百度之后才知道的 ，這個(gè)是關(guān)鍵，直接砍掉一般的時(shí)間

/*
ID:fuxiang2
PROG: checker
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <list>
#include <algorithm>
#include <set>
#include <cmath>
#include <cstring>
#include <cstdlib>
 
#define REP(i, n) for (int i=0;i<int(n);++i)
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)
#define EACH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)
 
using namespace std;
ofstream fout ("checker.out");
ifstream fin ("checker.in");
 
const int N = 14;
int graph[N][N];
int n;
int ans ;
int result ;
// 類(lèi)似八皇后問(wèn)題
int used[N];
//list <int >path;
int path[N];
 
bool isok(int x,int y)
{
    if(x >=1 && x<= n && y >= 1 && y <= n)
        return true;
    return false;
}
int dir[4][2] = { {-1,-1} ,{-1,1},{1,1},{1,-1} };
bool check(int x,int y )
{
    int nx = x;
    int ny = y;
    int n = x -1;
    if(n == 0)
        return true;
 
    FOR_1(i,1,n){
        nx = i;
        ny = path[i];
        if( abs(x-nx) == abs(y-ny))
            return false;
    }
    return true;
 
    //FOR_1(i,0,3){
    //    nx = x +  dir[i][0];
    //    ny = y +  dir[i][1];
    //    while(isok(nx,ny) ){
    //        if(graph[nx][ny] == 1)
    //            return false;
    //        nx += dir[i][0];
    //        ny += dir[i][1];
    //    }
    //}
    //return true;
 
}
 
void place(int col,int row)
{
    graph[row][col] = 1;
    if(row== n){
        ans ++;
        if(result + ans <= 3){
            //list<int >::iterator iter = path.begin();
            //fout<< *iter;
            fout<<path[1];
            //for(iter ++ ; iter != path.end() ; iter ++)
            for(int i = 2 ; i <= n ; i ++)
                fout <<" "<< path[i];
            fout<<endl;
        }
        graph[row][col] = 0;
        return ;
    }
    FOR_1(i,1,n){
        if(used[i] == 0 && check(row+1,i ) == true )
        {
            path[row+1] = i;//path.push_back(i);
            used[i] = 1;
            place(i,row+1);
            //path.pop_back();
            used[i] = 0;
        }
    }
    graph[row][col] = 0;
 
}
void work(int n)
{
    result = 0;
 
    FOR_1(j,1,n/2) {// 列
        path[1] = j;//path.push_back(j);
        used[j]  = 1;
        place(j,1);
        //path.pop_back();
        used[j] = 0;
    }
    int re =  ans;
    result = ans;
    if(re <3 || n%2 == 1){
        int t = n/2 + 1;
        ans = 0;
        path[1] = t;//path.push_back(j);
        used[t]  = 1;
        place(t,1);
 
    }
    if( n% 2 == 1)
        result += re + ans;
    else
        result += re;
}
 
int main()
{
    fin>>n;
    work(n);
    fout<< result<<endl;
    return 0;
 
}


原始博客地址： http://www.fuxiang90.com/2012/07/usaco1-5-checker-challenge/