[数据结构与算法]题目：codeforces 1510 K. King‘s Task（1200，dfs）

链接：https://codeforces.ml/problemset/problem/1510/K

题意：用两种操作对数组排序；

题解：dfs罗列所有情况；采用map+vector标记该状态是否出现过；

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans = INT_MAX;
map<vector<int>, int>mp;
void dfs(vector<int> num, int step)
{
	int key = 1;
	for (int i = 0; i < num.size(); i++)
	{
		if (num[i]!= i + 1)
		{
			key = 0;
			break;
		}
	}
	if (key == 1)
	{
		ans = min(step, ans);
	}
	vector<int>s1;
	for (int i = 0; i < num.size(); i += 2)
	{
		s1.push_back(num[i + 1]);
		s1.push_back(num[i]);
	}
	if (mp[s1] == 0)
	{
		mp[s1] = 1;
		dfs(s1, step + 1);
		mp[s1] = 0;
	}
	vector<int>s2;
	for (int i = num.size() / 2; i < num.size(); i++)
	{
		s2.push_back(num[i]);
	}
	for (int i = 0; i < num.size() / 2; i++)
	{
		s2.push_back(num[i]);
	}
	if (mp[s2] == 0)
	{
		mp[s2] = 1;
		dfs(s2, step + 1);
		mp[s2] = 0;
	}
}
int main() 
{
	int n;
	cin >> n;
	n *= 2;
	vector<int>x;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		x.push_back(a);
	}
	mp[x] = 1;
	dfs(x, 0);
	if (ans != INT_MAX)
		cout << ans << endl;
	else
		cout << -1 << endl;
}