回溯算法——八皇后问题

╰+攻爆jí腚メ 2021-07-16 21:25 540阅读 0赞

[八皇后问题（链接）][Link 1]

努比亚和苏丹没有子女，所以他要从一些有集成资格的继承者中挑选一个出来继承王位。他希望这个继承者足够聪明，所以他准备了一个西洋棋盘，上面的每个格子中均有一个  1 − 99 1-99 1−99 的数字。他又准备了  8 8 8 个皇后棋子。

8 8 8 皇后的规则就是不能有任何棋子同行或者同列或者同斜线，在满足这个规则的同时，王位继承者还需要让  8 8 8 个皇后所在的位置的数字的和是最大的。

输入格式

输入一个数字  k ( k ≤ 20 ) k(k\\leq 20) k(k≤20)，代表棋盘的数量。

接下来有  k k k 个棋盘，每个棋盘有  64 64 64 个数字，分成  8 8 8 行  8 8 8 列出入，具体可见样例，每一个数字均小于  100 100 100。  
输出格式

每一个棋盘对应输出最大的数值， 一共输出  k k k 行。

源码如下

#include<iostream>
    #include<vector>
    #include<map>
    #include<string>
    #include<algorithm>
    #pragma warning(disable:4996)
    using namespace std;
    typedef long long ll;
    int const Max = 1e2 + 5;
    int lst[Max][Max];
    int const Inf = 1e8 + 5;
    vector<int> vec;
    int sum;
    int cur[Max];//记录每一行皇后所在列
    
    void dfs(int h)//第h行
    { 
    	if (h == 9)//临界条件
    	{ 
    		sum = 0;
    		for (int i = 1; i <= 8; i++) sum += lst[i][cur[i]];
    		vec.push_back(sum);  //把每次结果加入vec
    		return;
    	}
    	for (int i = 1; i <= 8; i++)//把每一列尝试一遍
    	{ 
    		int flag = 1;
    		for (int j = 1; j < h; j++)
    		{ 
    			if (i == cur[j] || i + h == cur[j] + j || h - i == j - cur[j])//检查是否和前面的皇后冲突
    			{ 
    				flag = 0;
    				break;
    			}
    		}
    		cur[h] = i;//记录
    		if (flag) dfs(h + 1);//符合条件则进入下一行
    		cur[h] = 0;//抹除记录，这个问题里不写也可
    	}
    }
    
    int main()
    { 
    	int n;
    	cin >> n;
    	while (n--)
    	{ 
    		vec.clear();
    		for (int i = 1; i <= 8; i++)
    		{ 
    			for (int j = 1; j <= 8; j++) cin >> lst[i][j];
    		}
    		dfs(1);
    		sort(vec.begin(), vec.end(), greater<int>());//递减排序
    		cout << vec[0] << endl;
    	}
    }

[Link 1]: https://vjudge.net/problem/%E8%AE%A1%E8%92%9C%E5%AE%A2-381