广搜代码

#include <bits/stdc++.h>
using namespace std;
string s1,s2;
int l1,l2;
struct code{
	int a,b;
	int step; 
};
queue<code> q;
code u;
bool v[2005][2005];
void work(int a,int b){
	if(v[a][b]==0){
		v[a][b]=1;
		q.push({a,b,u.step+1});
	}
}
int bfs(){
	q.push({1,1,0});
	v[1][1]=1;
	while(!q.empty()){
		u=q.front();
		q.pop();
		if(u.a>l1 && u.b>l2) return u.step;
		if(u.a<=l1){
			int aa=u.a+1,bb=u.b;
			while(s1[aa]==s2[bb]){
				aa++,bb++;
			}
			if(aa!=(u.a+1) && bb!=(u.b)){
				work(aa,bb);
			}
			work(u.a+1,u.b);
		}
		if(u.b<=l2){
			int aa=u.a,bb=u.b+1;
			while(s1[aa]==s2[bb]){
				aa++,bb++;
			}
			if(aa!=(u.a) && bb!=(u.b+1)){
				work(aa,bb);
			}
			work(u.a,u.b+1);
		}
		if(u.a<=l1 && u.b<=l2){
			int aa=u.a+1,bb=u.b+1;
			while(s1[aa]==s2[bb]){
				aa++,bb++;
			}
			if(aa!=(u.a+1) && bb!=(u.b+1)){
				work(aa,bb);
			}
			work(u.a+1,u.b+1);
		}
	}
	return 1e9;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>s1>>s2;
	l1=s1.size();
	l2=s2.size();
	s1=" "+s1;
	s2=" "+s2;
	cout<<bfs()<<"\n";
	return 0;
}

AC记录