1.由于是北大OJ所以代码部分万能头文件不能用，整体思路就是按行枚举，找到‘#’同时判断对应行列标记数组是否已经被标记，本题唯一的坑在于，按行遍历的起始行需要在上一层的行数基础上+1枚举下一行，否则会导致后面的与前面重复配对，而且你还没来得及WA就TLE了。http://poj.org/problem?id=1321 

#include<iostream>
#include<stdio.h>
using namespace std;
char a[9][9];
int col[9]={0};
int n,k;
int sum=0;
void dfs(int u,int x)
{
    if(u==k)
    {
        sum++;
        return;
    }
    else
    {
        for(int i=x;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(a[i][j]=='#'&&!col[j])
                {
                    col[j]=1;
                    dfs(u+1,i+1);
                    col[j]=0;
                }
            }
        }
    }

}
int main()
{
    while(1)
    {
        scanf("%d%d",&n,&k);
        if(n==-1&&k==-1)
        {
            break;
        }
        else
        {
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    cin>>a[i][j];
                }
            }
        }
        dfs(0,0);
        printf("%d\n",sum);
        sum=0;
    }
    return 0;
}

2.暴力枚举+氧气优化（不优化TLE），和dfs没什么关系。https://www.luogu.com.cn/problem/P2105

#include<iostream>
#include<stdio.h>
#include<bits/stdc++.h>
#define N 20020
using namespace std;
int n,m,K;
int sum;
int a[N],b[N],c[N*2],d[N*2];
int main()
{
    scanf("%d%d%d",&n,&m,&K);
    for(int i=1;i<=K;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[x]=1;
        b[y]=1;
        c[x+y]=1;
        d[x-y+N]=1;
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]) continue;
            for(int j=1;j<=m;j++)
            {
                if(!a[i]&&!b[j]&&!c[i+j]&&!d[i-j+N])
                {
                    sum++;
                }
            }
    }
    printf("%d\n",sum);
    return 0;
}

  1. 下面的(x,y)相当于(u,i)
    （1）反对角线 y=x+b,截距b=y−x，因为我们要把b当做数组下标，所以 bb 不能是负的，所以我们 +n，保证是结果是正的
    （2）而对角线 y=−x+b,截距是 b=y+x这里截距一定是正的，所以不需要加偏移量
    核心目的：找一些合法的下标来表示dg或udg是否被标记过，所以如果你愿意，你取 udg[n+n−u+i]也可以，只要所有(u,i)对可以映射过去就行。
    https://www.luogu.com.cn/problem/P1219

    #include <bits/stdc++.h>
using namespace std;
const int N = 30;
// bool数组用来判断搜索的下一个位置是否可行
// col列，dg对角线，udg反对角线
// g[N][N]用来存路径
int n;
int g[N];
bool col[N], dg[N], udg[N];
int sum=0;
void dfs(int u)
{
 // u == n 表示已经搜了n行，故输出这条路径
 if (u == n)
 {
     if(sum<3)
     {
         for (int i = 0; i < n; i ++ ) printf("%d ",g[i]);   // 等价于cout << g[i] << endl;
         puts("");  // 换行       
     }
     sum++;
     return;
 }

 //对n个位置按行搜索
 for (int i = 0; i < n; i ++ )
     // 剪枝(对于不满足要求的点，不再继续往下搜索)              udg[n - u + i]，+n是为了保证大于0
     if (!col[i] && !dg[u + i] && !udg[n - u + i])
     {
         g[u]=i+1;
         col[i] = dg[u + i] = udg[n - u + i] = true;
         dfs(u + 1);
         // 恢复现场 这步很关键
         col[i] = dg[u + i] = udg[n - u + i] = false;
     }
}
int main()
{
 cin >> n;
 dfs(0);
 printf("%d\n",sum);
 return 0;
}