posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

USACO 1.1.5 Checker Challenge

Posted on 2007-06-03 19:22 ZelluX 阅读(595) 评论(0)  编辑  收藏 所属分类: Algorithm
一开始什么优化都没有，过不了了（记得以前是可以的啊）
然后用了三个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;
}


只有注册用户登录后才能发表评论。
网站导航: