Categories

USACO 1.5.4 Checker Challenge

熬了许久,总算是把这题给过了。经典的八皇后问题。

看了许多人的程序,希望能受到一点启发,可是由于本人天生愚笨,看不懂。

所以按自己的思路敲了一个,用回溯做的。

第一次交:

Executing…

   Test 1: TEST OK [0.011 secs, 2840 KB]

   Test 2: TEST OK [0.000 secs, 2844 KB]

   Test 3: TEST OK [0.000 secs, 2844 KB]

   Test 4: TEST OK [0.000 secs, 2844 KB]

   Test 5: TEST OK [0.022 secs, 2844 KB]

   Test 6: TEST OK [0.043 secs, 2840 KB]

   Test 7: TEST OK [0.205 secs, 2840 KB]

> Run 8: Execution error: Your program (`checker’) used more than

        the allotted runtime of 1 seconds (it ended or was stopped at

        1.188 seconds) when presented with test case 8. It used 2844 KB of

        memory.

          —— Data for Run 8 ——

        13

          —————————-

    Test 8: RUNTIME 1.188>1 (2844 KB)

后来利用结果对称性进行了优化,只用搜索一半就可以了。


Executing...
    Test 1: TEST OK [0.000 secs, 2844 KB]
    Test 2: TEST OK [0.000 secs, 2844 KB]
    Test 3: TEST OK [0.000 secs, 2840 KB]
    Test 4: TEST OK [0.000 secs, 2844 KB]
    Test 5: TEST OK [0.011 secs, 2844 KB]
    Test 6: TEST OK [0.032 secs, 2840 KB]
    Test 7: TEST OK [0.108 secs, 2844 KB]
    Test 8: TEST OK [0.626 secs, 2844 KB]
 
All tests OK.

Your program (‘checker’) produced all correct answers! This is your

submission #4 for this problem. Congratulations!

源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/*
ID: tgh7281
LANG: C++
TASK: checker
*/
#include <iostream>
#include <fstream>
using namespace std;
 
bool ColCheck[13]={false}; //初始状态所有行均未放置皇后
bool sum[25]={false},diff[25]={false};
bool CanPlace(int row,int col,int N);
 
int main()
{
    ifstream fin("checker.in");
    ofstream fout("checker.out");
 
    int N;
    int queen[13]={0}; //第i个皇后的位置:i行,queen[i]列
    int row=0,col=0;
    int total=0,total1=0; //放置的方法总数
 
    fin>>N;
    while (row<n)
    {
        if (N>6&&queen[0]>(N-1)/2) break; //利用对称性优化
        while (col<n&&(!CanPlace(row,col,N))) col++;
        if (col<n) //放置
        {
            queen[row]=col;
            ColCheck[col]=true; //第col列已放置皇后
            sum[row+col]=true;
            diff[row-col+N-1]=true;
            row++;
//col=0;
 
            if (row>=N)
            {
//输出
                total++;
                if (N%2)
                {
                    if (queen[0]==N/2) total1++;
                    else total1+=2;
                }
                else
                {
                    total1+=2;
                }
 
                if (total<=3)
                {
                    for (int i=0;i<n;i++)
                    {
                        fout<<queen[i]+1;
                        if (i<n-1) fout<<’ ‘;
                    }
                    fout<<endl;
                }
 
                ColCheck[queen[N-1]]=false;
                sum[N-1+queen[N-1]]=false;
                diff[2*N-2-queen[N-1]]=false;
                row=N-1;
                col++;
            }
            else col=0;
        }
        else //回溯
        {
            row–;
            if (row<0) break;
            col=queen[row]+1;
            ColCheck[queen[row]]=false;
            sum[row+queen[row]]=false;
            diff[row-queen[row]+N-1]=false;
        }
    }
    fout<<(N>6?total1:total)<<endl;
 
    fin.close();
    fout.close();
 
    return 0;
}
 
bool CanPlace(int row,int col,int N)
{
    if (ColCheck[col]||sum[row+col]||diff[row-col+N-1]) return false;
 
    return true;
}

1 comment to USACO 1.5.4 Checker Challenge

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

  

  

  

*