付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0

原始博客地址: http://www.fuxiang90.com/2012/07/usaco1-5-checker-challenge/拿到题目我的第一反应是八皇后问题,顺利的写出了递归解法,弄完这个,感觉自己写递归和回溯有了一定的进步了,至此第一章做完了,再接再厉。

但是提交后,在13 这个测试样例超时,然后就在想怎么剪枝

  • 之前在判断放棋子是否冲突的时候,是在放的位置往四个方向拓展,如果没有冲突就放 。现在改进为直接判断 和之前放置的棋子是否冲突。
  • 对称剪枝,这个在百度之后才知道的 ,这个是关键,直接砍掉一般的时间
还有说是用位运算,这个不熟,下次去学一下。
/*
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 ;
// 类似八皇后问题
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/
posted on 2012-07-10 10:41 付翔 阅读(164) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2012年7月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜