复兴提高班第二十三课 综合练习（三）
2025-10-31 12:48:59
发布于：上海
8阅读
0回复
0点赞
T1八皇后 Checker Challenge
#include<bits/stdc++.h>
using namespace std;
int a[1000],b[1000],c[1000],d[1000],n,s;
//a存行
//b存列
//c存左下到右上的对角线（行+列的和相同）
//d存右下到左上的对角线（行-列的差相同）
//清零数组
void print(){
int i;s++;
if(s<=3){
for(i=1;i<=n;i++)cout<<a[i]<<" ";
cout<<endl;
}
}
int search(int i){
int j;
for(j=1;j<=n;j++)
if(b[j]= =0&&c[i+j]= =0&&d[i-j+n]= =0){//判断
a[i]=j;//写进去（第i行第j个）
b[j]=1;//占行
c[i+j]=1; d[i-j+n]=1;//占对角线
if(i==n)print();//满足条件输出
else search(i+1);//继续推
b[j]=0;c[i+j]=0;d[i-j+n]=0;//回溯
}
return 0;
}
int main(){
cin>>n;
search(1);
cout<<s<<endl;
return 0;
}
T2【广度优先搜索(三)】打开转盘锁
#include <bits/stdc++.h>
using namespace std;
struct node {
int num[4];
int step;
} first, last;
int vis[10][10][10][10];
int bfs() {
int temp1, temp2;
node a, next;
a = first;
a.step = 0;
// 队首元素压入队列
queue<node> q;
q.push(a);
// 标记队首元素以及走过
vis[a.num[0]][a.num[1]][a.num[2]][a.num[3]] = 1;
while (!q.empty()) {
a = q.front();
q.pop();
// 退出条件
if (a.num[0] == last.num[0] && a.num[1] == last.num[1] && a.num[2] == last.num[2] && a.num[3] == last.num[3])
return a.step;
//+1操作
for (int i = 0; i < 4; i++) {
next = a;
next.num[i]++;
if (next.num[i] == 10) {
next.num[i] = 1;
}
if (!vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]) {
vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]] = 1;
next.step++;
q.push(next);
}
}
//-1操作
for (int i = 0; i < 4; i++) {
next = a;
next.num[i]--;
if (next.num[i] == 0) {
next.num[i] = 9;
}
if (!vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]) {
vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]] = 1;
next.step++;
q.push(next);
}
}
}
}
int main() {
// 每个数字有2个状态：1、加一 2、减一
// 当将9加1时，数字变为1，当1减1时，数字变为9.还可以交换相邻的数字，每一个行动记做一步
int i;
char str1[5], str2[5];
cin >> str1 >> str2;
for (i = 0; i < strlen(str1); i++) {
first.num[i] = str1[i] - '0';
last.num[i] = str2[i] - '0';
}
int ans = bfs();
cout << ans << endl;
return 0;
}
T3【综合练习(一)】Cow Travelling S
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10;
int to[4][2]= {-1,0,0,1,1,0,0,-1};
int n,m,t;
char mp[N][N]; //.为草地 *为障碍
int a[N][N];
int bx,by,ex,ey;
int res;
int dp[N][N][20];
int dfs(int x,int y,int step)
{
if(step>t) //剪枝1
return 0;
if(step+fabs(x-ex)+fabs(y-ey)>t) //剪枝2，走到(x,y),已经走了T秒，若(x,y)到目标点(ex,ey)的最短距离花费的总时间>t,则直接返回
return 0;
if(dp[x][y][step])
return dp[x][y][step];
if(x==ex&&y==ey&&step==t) //奶牛总是在移动，结束条件是刚好走了t秒 ,可以重复走
return 1;
int sum=0;
for(int i=0; i<4; i++)
{
int tx=x+to[i][0];
int ty=y+to[i][1];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]==1)
sum+=dfs(tx,ty,step+1);
}
dp[x][y][step]=sum;
return sum;
}
int main()
{
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
cin>>n>>m>>t; //地图n*m t秒 (R1,C1)-->(R2,C2)
for(int i=0; i<n; i++)
cin>>mp[i];
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(mp[i][j]=='*')
a[i+1][j+1]=0;
else
a[i+1][j+1]=1; //1能走、0不能走
}
}
cin>>bx>>by>>ex>>ey;
cout<<dfs(bx,by,0);
return 0;
}
T4变化的数字
#include <bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int a,end_num,len,step[N],ans=-1;
bool vis[N];
queue<int> q;
int getlen(int now){
int cnt=0;
while(now){
cnt++;
now/=10;
}
return cnt;
}
void bfs(){
q.push(1);
vis[1]=1;
while(!q.empty()){
int it=q.front();
q.pop();
if(it==end_num){
ans=step[it];
cout<<ans;
return;
}
int now=it*a;
if(getlen(end_num)>=getlen(now)){
if(vis[now]==0){
vis[now]=1;
step[now]=step[it]+1;
q.push(now);
}
}
if(it<10||it%10==0)continue;
long long mod=1;
mod=pow(10,getlen(it)-1);
now=(it%10)*mod+it/10;
if(vis[now]==0){
vis[now]=1;
step[now]=step[it]+1;
q.push(now);
}
}
cout<<ans;
}
int main(){
cin>>a>>end_num;
bfs();
return 0;
}
T5石子谜题
#include <bits/stdc++.h>
using namespace std;
map<string,int>mp;
string s1,s2;
int n;
queue<string>q;
int bfs(string x){
q.push(x);
mp[x]=1;
while(q.size()){
string t=q.front();
q.pop();
if (t==s2){
return mp[t]-1;
}
int kong;
for (int i=0;i<t.size()-1;i++){
if (t[i]=='.'){
kong=i;
break;
}
}
for (int i=0;i<t.size()-1;i++){
if (i==kong-1 || i==kong || i==kong+1){
continue;
}
string nt=t;
swap(nt[i],nt[kong]);
swap(nt[i+1],nt[kong+1]);
if (mp[nt]){
continue;
}
mp[nt]=mp[t]+1;
q.push(nt);
}
}
return -1;
}
int main() {
cin>>n;
n+=2;
cin>>s1>>s2;
if (s1.size()!=s2.size()){
cout<<-1;
return 0;
}
s1+="..";
s2+="..";
cout<<bfs(s1);
return 0;
}
有帮助，赞一个