Snowdream

posts - 403, comments - 310, trackbacks - 0, articles - 7

BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理

USACO 1.1.5 Checker Challenge

Posted on 2007-06-03 19:22 ZelluX 閱讀(603) 評論(0) 編輯收藏所屬分類: Algorithm

一開始什么優化都沒有，過不了了（記得以前是可以的?。?br>然后用了三個hash數組記錄各列、對角線棋子的放置情況，再加上左右對稱解的優化，總算在0.828秒里過了

PROG: checker

ID: 06301031

LANG: C++

#include <iostream>

#include <fstream>

using namespace std;

int g[13];

bool column[13], diag1[25], diag2[25];

int n;

int countResult = 0;

int mid = 0, firstHalf = 0;

ifstream fin("checker.in");

ofstream fout("checker.out");

void DFS(int t) {

int i;

if (t == n) {

countResult++;

if (countResult <= 3) {

fout << g[0] + 1;

for (i = 1; i < n; i++) {

fout << " " << g[i] + 1;

}

fout << endl;

}

return;

}

for (g[t] = 0; g[t] < n; g[t]++) {

if ((countResult > 3) && (t == 0)) {

if (g[t] == n / 2) {

firstHalf = countResult;

if (n % 2 == 0) {

fout << firstHalf * 2 << endl;

exit(0);

}

if ((g[t] == n / 2 + 1) && (n % 2 == 1)) {

mid = countResult - firstHalf;

fout << firstHalf * 2 + mid << endl;

exit(0);

}

if (column[g[t]]) {

continue;

}

if (diag1[g[t] + t]) {

continue;

}

if (diag2[g[t] - t + n]) {

continue;

}

diag1[g[t] + t] = true;

diag2[g[t] - t + n] = true;

column[g[t]] = true;

DFS(t + 1);

diag1[g[t] + t] = false;

diag2[g[t] - t + n] = false;

column[g[t]] = false;

nextPosition:

;

}

int main() {

fin >> n;

int i;

for (i = 0; i < n; i++) {

column[i] = false;

}

for (i = 0; i < n * 2 -1; i++) {

diag1[i] = false;

diag2[i] = false;

}

DFS(0);

fout << countResult << endl;

fout.close();

return 0;

}

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 函數式編程另類指南[zz] URAL 1011 Sorting Networks URAL 題解 - wiki 《編程之美》上的一道題目的討論求n個32位無符號整數中異或后值最大的兩個數 SICP 習題記錄 (1) 正則表達式的復雜度 Minesweeper is NP-complete Tom Duff on Duff's Device

Snowdream

USACO 1.1.5 Checker Challenge

日歷

常用鏈接

留言簿(21)

隨筆分類(390)

隨筆檔案(389)

文章檔案(7)

相冊

15ers

友情鏈接

收藏夾

搜索

積分與排名

最新隨筆

最新評論

閱讀排行榜

評論排行榜