百练 OJ 2754 八皇后问题

这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。

//转载请写上本帖链接:http://www.wutianqi.com/?p=169 //及【C++奋斗乐园/ACM乐园】

/**************************************** ID: 百练 OJ 2754 八皇后问题题目地址： http://poj.grids.cn/problem/2754/ My Name: Tanky_Woo My Website: C++奋斗乐园|C++学习|算法学习|ACM/ICPC学习 Website Link: http://www.cpply.com/

My BBS: C++奋斗乐园|C++论坛|算法论坛|ACM/ICPC论坛 BBS Link：http://www.cppleyuan.com/

My Blog：www.wutianqi.com 豆瓣小组：http://www.douban.com/group/cppleyuan/ QQ:17611904 QQ群：C++奋斗乐园①群：19333724（满） ②群：23840480 (满） ③群：17314377 ④群：23829384 *****************************************/

//方法一：此方法不用8*8的仿真棋盘来模拟控制区域，而只用一个有8个元素的数组记录已经摆放的棋子摆在什么位置，当要放置一个新的棋子时，只需要判断它与已经放置的棋子之间是否冲突就可以了。 //内存: 1848kb 时间: 0ms

 #include 
using namespace std;
int ans[92][8], hang[8], num = 0;


int queen(int i)
{
    int j, k;
    if(i == 8)   //一组新的解产生
    {
        for(j = 0; j < 8; j++)
            ans[num][j] = hang[j] + 1;
        num++;
        //memset(hang, 0, sizeof(hang));  这个地方还不能置0
    }
    if(num == 93)
        return 0;
    for(j = 0; j < 8; j++)   //将当前皇后i逐一尝试放在不同的列
    {
        for(k = 0; k < i; k++)  //逐一判定i与前面的皇后是否冲突
            if(hang[k] == j || (k-i) == (hang[k]-j) || (i-k)==(hang[k]-j))
                break;
        if(k == i)
        {
            hang[i] = j;
            queen(i+1);
            hang[i] = 0;  //加了这步后由16ms变成0ms
        }
    }
}

int main()
{
    num = 0;
    queen(0);
    int n;
    scanf("%d", &n;);
    for(int i = 0; i < n; i++)
    {
        int b;
        scanf("%d", &b;);
        for(int j = 0; j < 8; j++)
            printf("%d", ans[b-1][j]);
        printf("\n");
    }
    return 0;
}

方法二：用三个一维数组来分别记录每一列，每个45度的斜线，每个135度的斜线上是否已经被放置的棋子控制。

 #include 
using namespace std;

int record[92][9], mark[9], count = 0;
bool range[9], line1[17], line2[17];

void tryToPut(int n);
int main()
{
    int i, nCases, num;
    scanf("%d", &nCases;);

    for(i = 0; i <= 8; i++)
        range[i] = true;
    for(i = 0; i < 17; i++)
        line1[i] = line2[i] = true;

    tryToPut(1);

    while(nCases--)
    {
        scanf("%d", &num;);
        for(i = 1;i <= 8; i++)
            printf("%d", record[num-1][i]);
        printf("\n");
    }
    return 0;
}

void tryToPut(int i)
{
    if(i > 8)
    {
        for(int k = 1; k < 9; k++)
            record[count][k] = mark[k];
        count++;
    }
    for(int j = 1; j <= 8; j++)
    {
        if(range[j] && line1[i+j] && line2[i-j+9])
        {
            mark[i] = j;
            range[j] = line1[i+j] = line2[i-j+9] = false;
            tryToPut(i+1);
            range[j] = line1[i+j] = line2[i-j+9] = true;
        }
    }
}