题目一:串变换
代码解析:
#include <iostream>
using namespace std;
struct Option{
int select;
int x;
int y;
};
string S,T;
int N,K;//N是串的长度,K是操作指令的大小
Option opt[10];//存储所有的指令
bool vis[10];//标记数组,重要;
bool flag;//标记是否找到最终答案
void dfs(string s,int start)//以start为起点开始进行dfs
{
if(flag)return;//如果找到了最终答案,直接退出
vis[start]=true;//进行标记
int x=opt[start].x;
int y=opt[start].y;
if(opt[start].select==1)//注意此处要将字符转为数字再转回字符
{
int tmp=(int)(s[x]-'0');
tmp=(tmp+y)%10;
s[x]=(char)(tmp+'0');
}
else
{
swap(s[x],s[y]);
}
if(s==T)//S已经变成T,标志位置1并返回
{
flag=1;
return;
}
for(int i=1;i<=K;i++)//开始递归
{
string ss;
if(i==start)continue;
if(vis[i]==0)//该结点之前未访问
{
ss=s;//将s串复制一份
dfs(ss,i);
vis[i]=false;//退出递归后将第i个结点的标志位置回0
}
}
}
int main()
{
string temp_S;
cin>>N;
cin>>S>>T;
temp_S=S;//temp_S用于将S串复制一份用于传参
cin>>K;
for(int i=1;i<=K;i++)
{
cin>>opt[i].select>>opt[i].x>>opt[i].y;
}
for(int i=1;i<=K;i++)//把每个结点分别作为起点,进行K次dfs
{
vis[10]={0};
temp_S=S;
dfs(temp_S,i);
if(flag)
{
cout<<"Yes"<<endl;
break;
}
}
if(flag==0)cout<<"No"<<endl;
return 0;
}
题目二:玩具蛇
#include "iostream"
using namespace std;
int dx[4]={1,0,-1,0}; //方向控制类型
int dy[4]={0,1,0,-1};
int a[4][4]={0};
int n=0;
void dfs(int stay,int x,int y) //x,y相当于正在放置的格子的坐标
{
int tx,ty;
if(stay==16) //递归终止条件
{
n++;
return;
}
for(int i=0;i<4;i++) //尝试向四个方向放置
{
tx=x+dx[i]; //方向
ty=y+dy[i];
if(a[tx][ty]==1||tx<0||tx>3||ty<0||ty>3) //该格子不可放置 或越界 跳过该方向
continue;
a[tx][ty]=1; // 对已放置的格子进行标记
dfs(stay+1,tx,ty);
a[tx][ty]=0; //清除标记
}
}
int main()
{
void dfs(int stay,int x,int y);
int stay=0; //玩具蛇共16节 已放置了stay节
int i,k;
for(i=0;i<4;i++) //对4x4的格子 枚举玩具蛇第一个步放置的所有可能。
{
for(k=0;k<4;k++)
{
a[i][k]=1; //对已放置的格子进行标记
dfs(1,i,k);
a[i][k]=0; //清除标记
}
}
cout<<n;
return 0;
}
分糖果
代码及其解析
#include <iostream>
using namespace std;
int res = 0;
void dfs(int k,int tan1,int tan2)// 第i人选,糖果1,2数量
{
if(k>=7){ // 枚举完了,看糖果数
if(!tan1 && !tan2)res++;
return ;
}
for(int i=0;i<=tan1;i++) // 枚举糖1
for(int j=0;j<=tan2;j++) // 枚举糖2
if(i+j>=2 && i+j<=5)
dfs(k+1,tan1-i,tan2-j);
return ;
}
int main()
{
dfs(0,9,16);
cout<<res;
return 0;
}