算法刷题-回溯

今天给大家分享的还是一道关于dfs回溯的问题，对于这类问题大家还是要多刷和总结，总体难度还是偏大。

对于回溯问题有几个关键点：

1.首先对于这类回溯可以节点可以随机选择的问题，要做mian函数中循环调用dfs（i，obj），同时在dfs中要对后面的节点再次进行调用，还是使用dfs。

2.对于使用过的节点用vis进行记录，而递归出口则是flag。

3.注意在dfs选择后，要对这一次的递归选择进行回溯，下面这道题在dfs内的调用以及main函数中的调用都有显示。

问题描述

有两个长度为 n的数字字符串S,T ，下标从 0 开始。

一共有 k 个操作，操作只可能是以下两种类型：

• 1 x v 表示将 Sx​ 变为 (Sx+v)mod10；
• 2 x y 表示交换 Sx，Sy​。

你可以挑选出任意个操作，以任意顺序执行，但是每个操作最多只能执行一次，如果可以将 S 串变为 T 串则输出 Yes，反之输出 No。

输入格式

第一行输入一个正整数 n，表示字符串S 和  T的长度。

第二行输入一个长度为 n 只由数字构成的字符串 S。

第三行输入一个长度为 n 只由数字构成的字符串 T。

第四行输入一个正整数 k，表示操作的数量。

接下来 k 行，每行三个整数，其中第 i行表示第 i种操作的三个参数 opi​,xi​,yi​。

输出格式

一行一个字符串：

• 如果可以通过操作使得 S 串与 T 串相等，则输出 Yes。
• 反之输出 No。

代码部分：

#include <bits/stdc++.h>
using namespace std;
int a[11],b[11],c[11];
bool flag;
bool vis[11];
string s,t;
int n,k;
void dfs(string s,int start){vis[start]=1;if(a[start]==1){s[b[start]]=(s[b[start]]-'0'+c[start])%10+'0';}else swap(s[b[start]],s[c[start]]);if(s==t){flag=true;return;}for(int i=1;i<=k;i++){if(vis[i])continue;string ss=s;dfs(s,i);vis[i]=false;s=ss;}
}int main()
{cin>>n;cin>>s>>t;cin>>k;for(int i=1;i<=k;i++){cin>>a[i]>>b[i]>>c[i];}for(int i=1;i<=k;i++){if(flag)break;string _s=s;memset(vis,false,sizeof(vis));dfs(_s,i);}if(flag==true)cout<<"Yes"<<'\n';else cout<<"No"<<'\n';return 0;
}

然后这道题要注意mod10，我一开始做的时候就是忽略了这一部分，导致测试点有些部分没有通过。

好了，今天的分享就到这里，希望大家可以多多关注博主哦。