3-14

[蓝桥杯2017初赛]青蛙跳杯子

题目描述
X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。
X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。
如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。
WWWBBB
其中，W字母表示白色青蛙，B表示黑色青蛙，表示空杯子。
X星的青蛙很有些癖好，它们只做3个动作之一

1. 跳到相邻的空杯子里。
2. 隔着1只其它的青蛙（随便什么颜色）跳到空杯子里。
3. 隔着2只其它的青蛙（随便什么颜色）跳到空杯子里。
   对于上图的局面，只要1步，就可跳成该局面：WWW*BBB
   本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。

输入
输入存在多组测试数据，对于每组测试数据：
输入为2行，2个串，表示初始局面和目标局面。输入的串的长度不超过15
输出
对于每组测试数据：输出要求为一个整数，表示至少需要多少步的青蛙跳。
样例输入
WWBB
WWBB
WWWBBB
BBBWWW

样例输出
2
10

思路：
BFS，起始状态

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


string st,ed; 

map<string,int> mp;

int dx[6]={1,-1,2,-2,3,-3};


int main(){
	while(cin>>st>>ed){
		int ans=0;
		queue<pair<string,int> > que;
		que.push(make_pair(st,0));
		while(que.size()){
			string tmp=que.front().first;
			int step=que.front().second;
			que.pop();
			if(mp[tmp]==1){
				continue;
			}
			mp[tmp]=1;
			if(tmp==ed){
				ans=step;
				break;
			}
			int now;
			for(int i=0;i<tmp.size();i++){
				if(tmp[i]=='*'){
					now=i;
				}
			}
			for(int i=0;i<6;i++){
				int nw=now+dx[i];
				if(nw>=0&&nw<tmp.size()){
					swap(tmp[now],tmp[nw]);
					if(mp[tmp]==0){
						que.push(make_pair(tmp,step+1));
					}
					swap(tmp[now],tmp[nw]);
				}
			}
			
		}
		while(que.size()){
			que.pop();
		}
		mp.clear();
		cout<<ans<<endl;
	}
}

[蓝桥杯2017初赛]9数算式

题目描述
观察如下的算式：9213 x 85674 = 789314562
左边的乘数和被乘数正好用到了1~9的所有数字，每个1次。
而乘积恰好也是用到了1~9的所有数字，并且每个1次。
请你借助计算机的强大计算能力，找出满足如上要求的9数算式一共有多少个？
注意：

1. 总数目包含题目给出的那个示例。
2. 乘数和被乘数交换后作为同一方案来看待。

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

思路：全排列

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


int a[9]={1,2,3,4,5,6,7,8,9};
int vis[10];


bool fun(ll c){
	bool flag=1;
	while(c>0&&c<999999999){
		int tmp=c%10;
		c/=10;
		vis[tmp]++;
	}
	for(int i=1;i<=9;i++){
		if(vis[i]!=1){
			flag=0;
			break;
		}
	}
	return flag;
}


int main(){
	/*ll ans=0;
	do{
		
		ll aa,bb,cc;
		for(int i=1;i<5;i++){
			aa=0;
			bb=0;
			for(int j=0;j<i;j++){
				aa*=10;
				aa+=a[j];
			}
			for(int k=i;k<9;k++){
				bb*=10;
				bb+=a[k];
			}
		 cc=aa*bb;
	
			memset(vis,0,sizeof(vis));
			if(fun(cc)){
			//	cout<<aa<<endl;
			//	cout<<bb<<endl;
			//	cout<<cc<<endl;
			//	cout<<"---------------------------"<<endl;
				ans++;
			}
		}
		
	}while(next_permutation(a,a+9));*/
	cout<<1625<<endl;
}