3-12

[蓝桥杯2017初赛]跳蚱蜢

题目描述
如图所示： 有9只盘子，排成1个圆圈。其中8只盘子内装着8只蚱蜢，有一个是空盘。

我们把这些蚱蜢顺时针编号为 1~8。每只蚱蜢都可以跳到相邻的空盘中，也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。
请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列，并且保持空盘的位置不变（也就是1-8换位，2-7换位,…），至少要经过多少次跳跃？

输出
输出一个整数表示答案

参考：https://www.cnblogs.com/-Ackerman/p/12245137.html

思路：
空盘子想象为9
起始状态为123456789，最终状态为876543219，
每一步可以想象为9跟距离小于等于2的数字交换位置，
bfs搜索出从起始状态到最终状态所需的最少步数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e9+5;

/*bool vis[MAX_N] ; 
int dir[4]={-1,1,2,-2};
int st=123456789,ed=876543219;
int a[9];
int ans=0;
int sum(){
	int res=0;
	for(int i=0;i<9;i++){
		res*=10;
		res+=a[i];
	}
	return res;
}*/

int main(){
	/*queue<pair<int,int> > que;
	que.push(make_pair(st,0));
	while(que.size()){
		int x=que.front().first;
		int step=que.front().second;
		que.pop();
		if(vis[x]){
			continue;
		}
		vis[x]=1;
		if(x==ed){
			ans=step;
			break;
		}
		int j=8,now;
		while(x){
			if(x%10==9) now=j;
			a[j--]=x%10;
			x/=10;
		}
		for(int i=0;i<4;i++){
			swap(a[now],a[(now+dir[i]+9)%9]);
			int val=sum();
			if(vis[val]!=1){
				que.push(make_pair(val,step+1));
			}
			swap(a[now],a[(now+dir[i]+9)%9]);
		}
		
	}
	printf("%d\n",ans);*/
	cout<<20<<endl;
}

[蓝桥杯2017初赛]方格分割

题目描述
6x6的方格，沿着格子的边线剪开成两部分。要求这两部分的形状完全相同。如图就是可行的分割法。



试计算：包括这3种分法在内，一共有多少种不同的分割方法。注意：旋转对称的属于同一种分割法。

输出
输出一个整数表示答案

从中心对称点(4,4)开始向四周搜索，走到边界答案+1，
搜索的时候，vis是对称的，且答案需要去掉旋转和对称的，需要除4

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e9+5;

bool vis[10][10];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ans=0;
void dfs(int x,int y){
	if(x<=1||x>=7||y<=1||y>=7){
		ans++;
		return ;
	}
	for(int i=0;i<=4;i++){
		int nx=x+dx[i]; int x2=8-nx;
		int ny=y+dy[i];	int y2=8-ny;
		if(nx>=1&&nx<=7&&ny>=1&&ny<=7&&!vis[nx][ny]){
			vis[nx][ny]=1;
			vis[x2][y2]=1;
			dfs(nx,ny);
			vis[nx][ny]=0;
			vis[x2][y2]=0;
		}
	} 
}

int main(){
	vis[4][4]=1;
	dfs(4,4);
	vis[4][4]=0;
	printf("%d\n",ans/4);
	 
}