子串变换

发表于 更新于 分类于

Problem’s Website

  • 字串变换

    Solution

  • 这道题是一道比较基础的搜索题，但要会用一个很方便的STL函数——string类型的replace()，不会的请点击这，其他就直接bfs就可以了。

    Code

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<map>
    using namespace std;
    int cnt=1;
    string st,end;
    string a[10],b[10];
    queue <string> q;
    queue <int> ans;
    map <string,bool> vis;
    namespace Dy {
    	void AKNOIP() {
    		cin>>st>>end;
    		while(cin>>a[cnt]>>b[cnt]) cnt++;
    		cnt--;
    		q.push(st); ans.push(0);
    		while(!q.empty()&&q.front()!=end&&ans.front()<=10) {
    			if(vis[q.front()]==1) {
    				q.pop(); ans.pop();
    				continue;
    			}
    			vis[q.front()]=1;
    			string now,noww;
    			int num;
    			for(int i=1; i<=cnt; i++) {
    				now=q.front();
    				while(1) {
    					num=now.find(a[i]);
    					if(num==-1) break;
    					noww=q.front();
    					noww.replace(num,a[i].length(),b[i]);
    					q.push(noww);
    					ans.push(ans.front()+1);
    					now[num]='&';
    				}
    			}
    			q.pop(); ans.pop();
    		}
    		if(q.empty()||ans.front()>10) {
    			printf("NO ANSWER!");
    			return ;
    		}
    		printf("%d",ans.front());
    	}
    };
    int main() {
    	Dy::AKNOIP();
    	return 0;
    }

rp++