zoj 2778 - Triangular N-Queens Problem

题目：在三角形的棋盘上放n皇后问题。

分析：找规律题目。依照题目的输出，能够看出构造法则；

先填奇数，后填偶数。以下我们仅仅要证明这样的构造的存在性就可以。

解法：先给出集体构造方法，从（1。n-f（n）+1）開始填充奇数点；

填充全部的（1+2k。n-f（n）+1+k）{当中f（n）就是最大填充数。1+2k<=n-f（n）+1+k} 。

之后開始从（2。n-f（n）+1+k+1）開始填充偶数点，因为奇数点仅仅能攻击奇数点。

偶数点仅仅能攻击偶数点，所以仅仅要保证每行一个皇后就能够了。

证明：我们仅仅须要证明从第n-f（n）+1行開始。每行都能够放一个皇后就能够了；

首先。依照上面的构造可知，如此构造。皇后是不能够互相攻击的。

然后，因为第i行有i个元素。所以有 1+2k<=n-f（n）+1+k。

解得。k <= n-f（n）>= f(n)/2，因此至少有一半是奇数点；

偶数点仅仅要插入到奇数点之间就能够构造了。构造成功。

说明：（2011-09-19 01:28）。

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

bool M[ 1001 ][ 1001 ];

int  F[ 1005 ];

int  A[ 668 ];

int  B[ 668 ];

int main()

{

    /* 递推公式

    memset( F, 0, sizeof( F ) );

    F[ 0 ] = 0;F[ 1 ] = 1;F[ 2 ] = 1;

    for ( int i = 3 ; i <= 1000 ; ++ i )

        F[ i ] = F[ i-3 ] + 2;

    */

    for ( int i = 1 ; i <= 1000 ; ++ i )

        F[ i ] = (2*i+1)/3;

    int c,n;

    while ( scanf("%d",&c) != EOF )

    for ( int t = 1 ; t <= c ; ++ t ) {

        memset( M, 0, sizeof( M ) );

        scanf("%d",&n);

        printf("%d %d %d\n",t,n,F[ n ]);

        int y = n-F[ n ]+1;

        int x = 1;

        for ( int i = 0 ; i < F[ n ] ; ++ i ) {

            A[ i ] = y;B[ i ] = x;

            M[ y ][ x ] = 1;

            y += 1;x += 2;

            if ( x > y ) x = 2;

        }

        /* 画图部分

        for ( int p = 1 ; p <= n ; ++ p ) {

            for ( int q = 0 ; q < n-p ; ++ q )

                printf(" ");

            for ( int q = 1 ; q <= p ; ++ q )

                if ( M[ p ][ q ] )

                printf("* ");

                else

                    printf("@ ");

            printf("\n");

        }

        */

        printf("[%d,%d]",A[ 0 ],B[ 0 ]);

        for ( int i = 1 ; i < F[ n ] ; ++ i ) {

            if ( i%8 == 0 ) printf("\n");

            else printf(" ");

            printf("[%d,%d]",A[ i ],B[ i ]);

        }

        printf("\n\n");

    }

    return 0;

}