CodeForces 906B Seating of Students【dfs】

题解给出了一个比较巧妙的构造的方法，但是这个题也可以直接dfs去做，只考虑不与前面的安排好的左边以及上面的数有相邻，那么就可以往下一直dfs，但是我们感觉这样的复杂度可能有一点问题，但是能够过，但是大数据的话，其实还是应该按照题解，把奇数列放在一起，偶数列放在一起这样。。

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
#define ll long long
#define pb(i) push_back(i)
#define mp make_pair
using namespace std;
const int maxn=2e5+50;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;
ll fpow(ll n, ll k, ll p = mod) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n%p; n = n * n%p;} return r;}
ll inv(ll a, ll p = mod) {return fpow(a, p - 2, p);}
//head
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int p[maxn],n,m;
bool check(int i,int j)
{
    int x1=i/m;
    int y1=i%m;
    int x2=j/m;
    int y2=j%m;
    for(int k=0;k<4;k++)
    {
        if(x1+dx[k]==x2&&y1+dy[k]==y2)return true;
    }
    return false;
}
bool dfs(int i)
{
    if(i==n*m)return true;
    int x=i/m;
    int y=i%m;
    for(int j=i;j<n*m;j++)
    {
        swap(p[i],p[j]);
        if(x&&check(p[i],p[(x-1)*m+y]))continue; //就是判断 交换位置之后的p[i]与周围的位置是否有冲突 
        if(y&&check(p[i],p[x*m+y-1]))continue;  // (x-1)*m+y 即为上面的 x*m+y-1即为左边的，因为我们每次都从i开始，向后交换
        if(dfs(i+1))return true;//所以只要考虑不与前面的数冲突即可
        swap(p[i],p[j]);
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n*m;i++) p[i]=i;
    if(dfs(0))
    {
        puts("YES");
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                printf("%d ",p[i*m+j]+1);
            }
            printf("\n");
        }
    }
    else puts("NO");
    return 0;
}