搜索与图论1

DFS(关键是顺序)

int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

例题：给定一个整数n，将数组1~n排成一排，将会有很多中排列方法。现在，请你按照字典序将所有排列方法输出。

输入：

3

输出：

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

#include <iostream>
using namespace std;
const int N = 10;
int n;
int path[N];
bool st[N];//看看这个点有没有被用过
void dfs(int u)
{
	if(u==n)//如果有方案了，就输出
	{
		for(int i=0;i<n;i++) printf("%d ",path[i]);
		puts("");
		return;
	} 
	for(int i=1;i<=n;i++)
		if(!st[i])//如果i没有被填过
		{
			path[u]=i;//把i填进去
			st[i]=true;//把第i个数标记为用过
			dfs(u+1);//用x++的话，一会还要x--，所以就用x+1省事
            //搜索下一层
			st[i]=false;
            //回溯(回复原来递归下一层前的现场)
		}
}
int main()
{
	cin >> n;
	dfs(0);//从0开始
	return 0;
}

n皇后

算法1:

(按行枚举) O(n!)

解释说明

对角线 dg[u+i]，反对角线udg[n−u+i]中的下标 u+i和 n−u+i 表示的是截距

下面的(x,y)相当于(u,i)

（1）反对角线 y=x+b, 截距 b=y−x，因为我们要把 b 当做数组下标，所以 b 不能是负的，所以我们 +n，保证是结果是正的

（2）而对角线 y=−x+b, 截距是 b=y+x，这里截距一定是正的，所以不需要加偏移量

核心目的：找一些合法的下标来表示dg或udg是否被标记过，所以如果你愿意，你取 udg[n+n−u+i] 也可以，只要所有(u,i)对可以映射过去就行

#include <iostream>
using namespace std;
const int N = 20;

// bool数组用来判断搜索的下一个位置是否可行
// col列，dg对角线，udg反对角线
// g[N][N]用来存路径

int n;
char g[N][N];
bool col[N], dg[N], udg[N];

void dfs(int u)
{
    // u == n 表示已经搜了n行，故输出这条路径
    if (u == n)
    {
        for (int i = 0; i < n; i ++ ) puts(g[i]);   // 等价于cout << g[i] << endl;
        puts("");  // 换行
        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] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            // 恢复现场 这步很关键
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';

        }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';

    dfs(0);

    return 0;
}   

算法2:

(按每个元素枚举) O(2的n的平方次)

时间复杂度分析：每个位置都有两种情况，总共有n^2个位置

// 不同搜索顺序 时间复杂度不同 所以搜索顺序很重要！

#include <iostream>
using namespace std;
const int N = 20;

// 因为是一个个搜索，所以加了row
int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N];

// s表示已经放上去的皇后个数
void dfs(int x, int y, int s)
{
    // 处理超出边界的情况
    if (y == n) y = 0, x ++ ;

    // 说明已经放好了n个皇后，表示枚举完 n^2 个了
    if (x == n)
    {
        if (s == n)
        {
            for (int i = 0; i < n; i ++ ) puts(g[i]);
            puts("");
        }
        return;
    }

    // 不放皇后  就往下搜下一个位置
    dfs(x, y + 1, s);

    // 放皇后
    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
    {
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
        g[x][y] = '.';
    }
}


int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';

    dfs(0, 0, 0);

    return 0;
}