NOIP2002 字串变换

题二字串变换（存盘名: NOIPG2）

[问题描述]:

　　已知有两个字串 A$, B$ 及一组字串变换的规则（至多6个规则）:

　　　　　A1$ -> B1$

　　　　　A2$ -> B2$

　　规则的含义为：在 A＄中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ …。

　　　　例如：A$＝'abcd'　B$＝'xyz'

　　变换规则为：

　　　　‘abc’->‘xu’　‘ud’->‘y’　‘y’->‘yz’

　　则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：

　　　‘abcd’->‘xud’->‘xy’->‘xyz’

　　共进行了三次变换，使得 A$ 变换为B$。

[输入]:

　　键盘输人文件名。文件格式如下：

　　　A$ B$

　　　A1$ B1$ \

　　　A2$ B2$? |-> 变换规则

　　　... ... /?

　　所有字符串长度的上限为 20。

[输出]:

　　输出至屏幕。格式如下：

　　若在 10 步（包含 10步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出"NO ANSWER!"

[输入输出样例]

b.in:

　abcd wyz

　abc xu

　ud y

　y yz

屏幕显示：

【思路】

Bfs。

隐式图的搜索，需要注意的是转移的时候状态u中可能有多处与A$匹配，也就是一个A$可以拓展多个点。

【代码】

#include<iostream>

#include<fstream>

#include<cstdlib>

#include<cstring>

#include<queue>

#include<map>

using namespace std;

const int maxn = 1000+10;

struct Node{

	string s;

	int d;

};

string block[maxn];

map<string,int> X;

string a[7],b[7];

string A,B;

int n=0;

int pos[maxn];

void make_pos(string s,string t) {

	pos[0]=1; int lens=s.size(),lent=t.size();

	for(int i=0;i<=lens-lent;i++)

	   if(s.substr(i,lent)==t)

	       pos[pos[0]++]=i;

}

void bfs() {

    queue<Node> q;

    q.push((Node){A,0});

    X[A]=1;

    while(!q.empty()) {

    	Node u=q.front(); q.pop();

    	if(u.s==B) { cout<<u.d; return ; }

    	for(int r=0;r<n;r++) {

    	    make_pos(u.s,a[r]);

    	    for(int i=1;i<pos[0];i++) {

    		    string s=u.s;

    			s.replace(pos[i],a[r].size(),b[r]);

    		    if(!X.count(s) && u.d+1<=10) {

    		    	X[s]=1;

    		    	q.push((Node){s,u.d+1});

    		    }

    		}

    	}

    }

    cout<<"NO ANSWER!";

}

int main() {

	ios::sync_with_stdio(false);

	freopen("NOIPG2.in","r",stdin);

	freopen("NOIPG2.out","w",stdout);

	cin>>A>>B;

	while(cin>>a[n]>>b[n]) n++;

	bfs();

	return 0;

}

找出所有字符串匹配点也可以用KMP算法，就本题数据而言优化效果不大

int f[maxn];

void get_Fail(string P) {

	int m=P.size();

	f[0]=f[1]=0;

	for(int i=1;i<m;i++) {

		int j=f[i];

		while(j && P[j]!=P[i]) j=f[j];

		f[i+1]=P[i]==P[j]?j+1:0;

	}

}

void KMP(string T,string P) {

	pos[0]=1;

	int n=T.size(),m=P.size();

	get_Fail(P);

	int j=0;

	for(int i=0;i<n;i++) {

		while(j && T[i]!=P[j]) j=f[j];

		if(T[i]==P[j]) j++;

		if(j==m) pos[pos[0]++]=i-m+1,j=0;  //i-m+1

	}

}

巴特西

NOIP2002 字串变换

最新文章

热门文章