一、八数码
在一个 3×3 的网格中,1∼8 这 8 个数字和一个
x
恰好不重不漏地分布在这 3×3 的网格中。例如:
1 2 3 x 4 6 7 5 8
在游戏过程中,可以把
x
与其上、下、左、右四个方向之一的数字交换(如果存在)。我们的目的是通过交换,使得网格变为如下排列(称为正确排列):
交换过程如下:
1 2 3 1 2 3 1 2 3 1 2 3 x 4 6 4 x 6 4 5 6 4 5 6 7 5 8 7 5 8 7 x 8 7 8 x
把
x
与上下左右方向数字交换的行动记录为u
、d
、l
、r
。现在,给你一个初始网格,请你通过最少的移动次数,得到正确排列。
输入格式
输入占一行,将3×3 的初始网格描绘出来。
例如,如果初始网格如下所示:
1 2 3 x 4 6 7 5 8
则输入为:
1 2 3 x 4 6 7 5 8
输出格式
输出占一行,包含一个字符串,表示得到正确排列的完整行动记录。
如果答案不唯一,输出任意一种合法方案即可。
如果不存在解决方案,则输出
unsolvable
。输入样例:
2 3 4 1 5 x 7 6 8
输出样例:
ullddrurdllurdruldr
参考代码:
#include<iostream>
#include<unordered_map>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
typedef pair<int,string> PIS;
string start,endd;
string op="udlr";
int ne[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int f(string now)
{
int ans=0;
for(int i=0;i<9;i++)
{
if(now[i]=='x') continue;
int m=now[i]-'1';
ans+=abs(i%3-m%3)+abs(i/3-m/3);
}
return ans;
}
string astar()
{
unordered_map<string,string> pre;
unordered_map<string,int> dist;
unordered_map<string,bool> st;
priority_queue<PIS,vector<PIS>,greater<PIS>> heap;
heap.push({f(start),start});
dist[start]=0;
pre[start]="";
while(heap.size())
{
auto it=heap.top();heap.pop();
string now=it.second;
if(now==endd) return pre[now];
if(st[now]) continue;
st[now]=true;
int k=now.find('x');
int x=k/3,y=k%3;
string source=now;
for(int i=0;i<=3;i++)
{
int tx=x+ne[i][0],ty=y+ne[i][1];
if(tx>=0&&tx<=2&&ty>=0&&ty<=2)
{
swap(now[k],now[tx*3+ty]);
if(!dist.count(now)||dist[now]>dist[source]+1)
{
dist[now]=dist[source]+1;
pre[now]=pre[source]+op[i];
heap.push({dist[now]+f(now),now});
}
now=source;
}
}
}
return "";
}
int main()
{
endd="12345678x";
string s;
for(int i=0;i<9;i++)
{
char ch;cin>>ch;
start+=ch;
if(ch!='x') s+=ch;
}
int sum=0;
for(int i=0;i<8;i++)
for(int j=i+1;j<8;j++)
if(s[i]>s[j]) sum++;
if(sum&1) cout<<"unsolvable";
else cout<<astar();
return 0;
}
二、单词接龙
单词接龙是一个与我们经常玩的成语接龙相类似的游戏。
现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”,每个单词最多被使用两次。
在两个单词相连时,其重合部分合为一部分,例如 beast 和 astonish ,如果接成一条龙则变为 beastonish。
我们可以任意选择重合部分的长度,但其长度必须大于等于1,且严格小于两个串的长度,例如 at 和 atide 间不能相连。
输入格式
输入的第一行为一个单独的整数 n 表示单词数,以下 n 行每行有一个单词(只含有大写或小写字母,长度不超过20),输入的最后一行为一个单个字符,表示“龙”开头的字母。
你可以假定以此字母开头的“龙”一定存在。
输出格式
只需输出以此字母开头的最长的“龙”的长度。
数据范围
n≤20,
单词随机生成。输入样例:
5 at touch cheat choose tact a
输出样例:
23
提示
连成的“龙”为 atoucheatactactouchoose。
参考代码:
#include<iostream>
#include<cstring>
using namespace std;
const int N=25;
string s[N];
int g[N][N],n,used[N],ans;
void dfs(string now,int last)
{
int len=now.size();
ans=max(ans,len);
used[last]++;
for(int i=0;i<n;i++)
{
if(g[last][i]&&used[i]<2)
{
string t=now+s[i].substr(g[last][i]);
dfs(t,i);
}
}
used[last]--;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>s[i];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
string a=s[i],b=s[j];
for(int k=1;k<min(a.size(),b.size());k++)
{
if(a.substr(a.size()-k,k)==b.substr(0,k))
{
g[i][j]=k;
break;
}
}
}
char c;cin>>c;
for(int i=0;i<n;i++)
if(c==s[i][0]) dfs(s[i],i);
cout<<ans;
}