求助大佬，87分最后一个tle

zcylanqiao @ 2024-03-30 11:41:28

/*********************************************************************

*********************************************************************/
#include <iostream>
using namespace std;

int attack[15][15], n, total = 0;
int position[15];

int dx[] = {1, -1, 0, 1};
int dy[] = {1, 1, 1, 0};

void dfs(int x, int y) {
    int xx, yy, tmp[15][15];

    if (x != 0 && y != 0) {
        for (int j = 0; j <= 3; j++) { //当前x,y可以进攻的位置
            for (int i = -1 * n; i < n; i++) {
                xx = x + i * dx[j];
                yy = y + i * dy[j];
                if ((xx >= 1 && xx <= n) && (yy >= 1 && yy <= n))
                    attack[xx][yy] = 1;
            }
        }
    }

    if (y == n) {
        total++;
        if (total <= 3) {
            for (int i = 1; i <= n; i++) {
                cout << position[i] << " ";
            }
            cout << endl;
        }
        return;
    }

    for (int j = 1; j <= n; j++) { //寻找当前x,y下一行剩余的位置
        if (!attack[j][y + 1]) {
            position[y + 1] = j;
            for (int a = 1; a <= n; a++) {
                for (int b = 1; b <= n; b++)
                    tmp[a][b] = attack[a][b];
            }
            dfs(j, y + 1);
            for (int a = 1; a <= n; a++) {
                for (int b = 1; b <= n; b++)
                    attack[a][b] = tmp[a][b];
            }
        }
    }
}

int main() {
    cin >> n;
    dfs(0, 0);
    cout << total;

    return 0;
}

by ycy1124 @ 2024-03-30 12:11:31

@zcylanqiao

#include<bits/stdc++.h>
using namespace std;
int n,js;
bool a[20][20];
bool pd(int i,int j)
{
    int x=i,y=j;
    while(x>=1)
    {
        x--;
        if(a[x][j])
        {
            return 0;
        }
    }
    x=i;
    while(x>=1&&y>=1)
    {
        x--;
        y--;
        if(a[x][y])
        {
            return 0;
        }
    }
    x=i;
    y=j;
    while(x>=1&&y<=n)
    {
        x--;
        y++;
        if(a[x][y])
        {
            return 0;
        }
    }
    return 1;
}
void dfs(int i)
{
    for(int j=1;j<=n;j++)
    {
        if(pd(i,j))
        {
            a[i][j]=1;
            if(i==n)
            {
                js++;
                if(js<=3)
                {
                    for(int x=1;x<=n;x++)
                    {
                        for(int y=1;y<=n;y++)
                        {
                            if(a[x][y])
                            {
                                cout<<y<<" ";
                            }
                        }
                    }
                    cout<<endl;
                }
                a[i][j]=0;
                return; 
            }
            dfs(i+1);
            a[i][j]=0;
        }
    }
}
int main()
{
    cin>>n;
    dfs(1);
    cout<<js;
    return 0;
}

by zcylanqiao @ 2024-03-30 15:40:10

@ycy1124 这pd函数不太懂

by ycy1124 @ 2024-03-30 15:43:04

@zcylanqiao

就是先判断当前走在这里会不会干扰到原来已经放好的棋子

by zcylanqiao @ 2024-03-30 15:54:58

@ycy1124 噢噢，感谢