题解

128 条题解

  • 2
    @ 2017-05-08 08:58:44
    /*
    很裸的一道搜索题啊
    我们看这个数据范围就知道不写搜索都对不起出题人了
    我们可以直接bfs+判重
    判重我们知道,我们可以用hash,set,map等方法来做咯
    这里为了好写一点
    就用的set映射来判重
    (闲的无聊实验证明了一下set会比map慢一点啊Orz)
    Orz还是速度还是可以的(不过NOIP最好还是手写hash叭)
    然后这样直接bfs就很简单了
    基本功吧
    整个题目唯一的稍微的难点就在于字符串的处理了
    感觉像是在考字符串?
    我们怎么找到一个字符串中有没有可以变换的子串然后改变它
    OTZ这很麻烦的鬼东西如果用数组的话
    但是如果我们用string就很好做了
    加上几个string的函数
    就跟水题一样如履平地233333
    然后随便乱搞叭
    嗯就这样了
    那段bfs扩展的字串处理有点复杂
    也可以用自己的方法搞咯
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    #include <set>
    using namespace std;
    
    struct node
    {
        string s;
        int step;
    };
    queue<node> q;
    set<string> vis;
    string start,to;
    string a[15];
    string b[15];
    int l=1;
    
    void init()
    {
        cin>>start>>to;
        while(cin>>a[l]>>b[l])
            l++;
        node t;
        t.step=0;
        t.s=start;
        q.push(t);
    }
    
    void bfs()
    {
        node t;
        while(!q.empty())
        {
            t=q.front();    q.pop();
            if(t.step>10)
                break;
            if(t.s==to)
            {
                cout<<t.step<<endl;
                return;
            }
            if(!vis.count(t.s))
            {
                vis.insert(t.s);
                for(int i=1;i<=l;i++)
                    if(t.s.find(a[i])>=0)
                        for(int j=t.s.find(a[i]);j>=0&&j<=(t.s.length()-a[i].length());j=t.s.find(a[i],j+1))
                        {
                            node w=t;
                            w.step++;
                            w.s.replace(j, a[i].size(), b[i]);
                            q.push(w);
                        }
            }
        }
        cout<<"NO ANSWER!"<<endl;
    }
    
    int main()
    {
        init();
        bfs();
        return 0;
    }
         
    
  • 1
    @ 2017-08-14 16:00:28

    低逼格题解。。。
    实际上就是字符串BFS

    #include <iostream>
    #include <algorithm>
    #include <queue>
    #include <map>
    #include <string>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    struct edgedata
    {
        string u,v;
    };
    struct quedata
    {
        string str;
        int tmp;
    };
    queue<quedata> que;
    map<string,bool> flag;
    edgedata edge[10];
    string strs,stre;
    char Cstr1[25],Cstr2[25];
    int edgesize;
    inline bool cmp(string &a,string &b)
    {
        if (a.size()!=b.size())
            return 0;
        for (int i=0;i<(int)a.size();i++)
            if (a[i]!=b[i])
                return 0;
        return 1;
    }
    inline int Read()
    {
        scanf("%s%s",Cstr1,Cstr2);
        strs=Cstr1,stre=Cstr2;
        for (edgesize=1;scanf("%s%s",Cstr1,Cstr2)!=EOF;edge[edgesize].u=Cstr1,edge[edgesize++].v=Cstr2);
        return --edgesize;
    }
    inline int Write(int arg)
    {
        if (arg==-1)
            printf("NO ANSWER!\n");
        else
            printf("%d\n",arg);
        return 0;
    }
    int Push(quedata u,int tmp)
    {
        int pushsize=0;
        for (int list=u.str.find(edge[tmp].u);list!=(int)string::npos;list=u.str.find(edge[tmp].u,list+1),pushsize++)
        {
            quedata v=u;
            v.tmp++;
            v.str.erase(list,edge[tmp].u.size());
            v.str.insert(list,edge[tmp].v);
            if (!flag[v.str])
                que.push(v);
            flag[v.str]=1;
        }
        return pushsize;
    }
    int Bfs()
    {
        for (;!que.empty();que.pop());
        quedata U;
        U.str=strs,U.tmp=0;
        que.push(U);
        for (;!que.empty();)
        {
            quedata u=que.front();
            que.pop();
            if (u.tmp>10)
                return -1;
            if (!strcmp(u.str.c_str(),stre.c_str()))
                return u.tmp;
            for (int i=1;i<=edgesize;i++)
                Push(u,i);
        }
        return -1;
    }
    int main()
    {
        Read();
        int ret=Bfs();
        Write(ret);
        return 0;
    }
    
  • 0
    @ 2018-03-28 11:51:41

    //bfs 和自己写的字符串处理。
    ```cpp
    #include <iostream>
    #include<cstring>
    #include<algorithm>
    #include <queue>
    #include <cstring>
    #include <vector>
    #include <map>
    #include <set>
    using namespace std;

    #define FileIn() freopen("input.txt","r",stdin);
    #define SUPER_BREAK() exit(0);
    #define test() cout << "OK \n" << flush;
    #define WC(x) cout << (x) << " " << flush << endl;

    const int MAXLEN = 75;
    const int MAX = 7;
    char start[MAXLEN],tar[MAXLEN];
    char a[MAX][MAXLEN],b[MAX][MAXLEN];
    int cnt = 0;
    set<string> vis;

    struct Node {
    string str;
    int step = 0;
    };

    vector<int> hasIt(const string &pattern,char *s2) {
    vector<int> v;
    int len1 = pattern.length(),len2 = strlen(s2);
    for(int i = 0,j = 0; i < len1; ++i) {
    if(i + len2 > len1) break;
    bool matched = true;
    for(j = 0; j < len2; ++j) {
    if(s2[j] != pattern[i+j]) {
    matched = false;
    break;
    }
    }
    if(matched) v.push_back(i);
    }
    return v;// 返回匹配的下标序列
    }

    int bfs() {
    queue<Node> q;
    Node s;
    s.str = string(start);
    q.push(s);
    vis.insert(s.str);

    while(!q.empty()) {
    Node u = q.front();
    q.pop();
    if(u.step > 10) return 0;
    if(u.str == tar)
    return u.step;

    vector<int> v;
    for(int i = 0; i < cnt; ++i) {
    Node nd;
    char buf[MAXLEN];
    nd.str = u.str;

    v = hasIt(u.str,a[i]);
    if(v.size()) {
    for(int k = 0; k < v.size(); ++k) { //串处理写的比较差
    int p = v[k];
    strcpy(buf,u.str.c_str());
    strcpy(buf+p,b[i]);
    if(strlen(buf) > 20) continue;
    strcpy(buf+p+strlen(b[i]),u.str.c_str()+p+strlen(a[i]));
    if(strlen(buf) > 20) continue;
    nd.str = string(buf);

    if(!vis.count(nd.str)) {
    nd.step = u.step + 1;
    q.push(nd);
    vis.insert(nd.str);
    }
    }
    }

    }
    }
    return 0;
    }

    int main(int argc, char const *argv[])
    {
    // FileIn();
    cin >> start >> tar;
    while(scanf(" %s %s",a[cnt],b[cnt]) != EOF) cnt ++;

    int ans = bfs();
    if(ans == 0) cout << "NO ANSWER!";
    else cout << ans;
    return 0;
    }
    ```

  • 0
    @ 2016-09-24 08:35:45

    Map判重,单向BFS,一开始数组开小了,Wrong Answer3个点
    ```
    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <queue>
    #include <map>

    using namespace std;

    string A, B;

    string from[10];
    string to[10];
    int n = 1;

    struct node
    {
    string s;
    int step;
    };

    queue<node> q;
    map<string, int> visit;

    void work()
    {
    int i, j;
    while (!q.empty())
    {
    struct node t;
    t = q.front();
    q.pop();
    if (t.s == B && t.step <= 10)
    {
    cout<<t.step<<endl;
    return;
    }
    if (t.step > 10)
    return;
    if (visit[t.s] == 0)
    {
    visit[t.s] = 1;
    for (i = 1; i <= n; i++)
    {
    if (t.s.find(from[i]) >= 0)
    {
    for (j = t.s.find(from[i]); j >= 0 && j <= t.s.size() - from[i].size(); j = t.s.find(from[i], j + 1))
    {
    struct node w;
    w = t;
    w.step++;
    w.s.replace(j, from[i].size(), to[i]);
    q.push(w);
    }
    }
    }
    }
    }
    cout<<"NO ANSWER!"<<endl;
    }

    int main()
    {
    node e;
    cin>>A>>B;
    while (cin>>from[n]>>to[n])n++;
    n--;
    e.s = A;
    e.step = 0;
    q.push(e);
    work();

    return 0;
    }
    ```

  • 0
    @ 2016-09-03 21:59:22

    数据很小不需要剪枝,直接bfs即可
    此题用STL做就如同做简单模拟题一样轻松
    ```c++
    #include<iostream>
    #include<cstdio>
    #include<map>
    #include<queue>
    #include<string>
    #include<vector>
    using namespace std;

    struct Transform {
    string from, to;
    Transform (const string &from, const string &to) : from(from), to(to) {}
    };

    string A, B;
    map<string, int> d;
    vector<Transform> transforms;

    bool bfs () {
    queue<string> Q;
    Q.push(A);
    d[A] = 0;
    while (!Q.empty()) {
    string u = Q.front(); Q.pop();
    if (d[u] > 10) return false;
    if (u == B) return true;
    for (int i = 0; i < transforms.size(); i++) {
    const Transform &tool = transforms[i];
    string C;
    int p = u.find(tool.from);
    while (p != string::npos) {
    C = u;
    C.replace(p, tool.from.size(), tool.to, 0, tool.to.size());
    if (!d.count(C)) {
    d[C] = d[u] + 1;
    Q.push(C);
    }
    p = u.find(tool.from, p+1);
    }
    }
    }
    return false;
    }

    int main ()
    {
    // freopen("in.txt", "r", stdin);
    cin >> A >> B;
    string from, to;
    while (cin >> from >> to) transforms.push_back(Transform(from, to));

    if (bfs()) cout << d[B] << "\n";
    else cout << "NO ANSWER!\n";
    return 0;
    }
    ```

  • 0
    @ 2016-08-08 10:38:41

    mdzz为什么加上algorithm就编译不过??窝的Rp啊!!
    - 测试数据 #0: Accepted, time = 0 ms, mem = 572 KiB, score = 10
    - 测试数据 #1: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    - 测试数据 #2: Accepted, time = 0 ms, mem = 572 KiB, score = 10
    - 测试数据 #3: Accepted, time = 0 ms, mem = 624 KiB, score = 10
    - 测试数据 #4: Accepted, time = 93 ms, mem = 1080 KiB, score = 10

    Accepted, time = 93 ms, mem = 1080 KiB, score = 50
    思路:迭代加深搜索+可行性剪枝。如果剩余步数为x时匹配str失败了,记mp[str] = x,那么当下一次匹配str且剩余步数少于mp[str],就注定失败。
    ```c++
    #include <iostream>
    #include <cstring>
    #include <map>
    #include <queue>
    using namespace std;
    string from, to;
    map<string, int> mp;
    string x[20], y[20];
    int n = 1;
    int lim = 1;
    bool dfs(const string& str, const int now_depth)
    {
    //cout << str << endl;
    if (now_depth > lim)
    return 0;
    if (str == to) return 1;
    if (lim - now_depth <= mp[str])
    return 0;
    //cout << str << endl;
    for (int k = 1; k < n; k++) {
    string::size_type pp, last = -1;
    string tmp = str;
    while (1) {
    pp = str.find(x[k], last+1);
    if (pp != string::npos) {
    tmp.replace(pp, x[k].size(), y[k]);
    //cout << tmp << endl;
    if (dfs(tmp, now_depth+1))
    return 1;
    //else mp[tmp] = max(mp[tmp], lim - now_depth-1);

    tmp = str;
    last = pp;
    } else break;
    }
    }
    mp[str] = max(mp[str], lim-now_depth);
    return 0;
    }

    int main()
    {
    cin >> from >> to;
    while (cin >> x[n] >> y[n]) n++;
    for (; lim <= 10; lim++) {
    if(dfs(from, 0)) {
    cout << lim << endl;
    return 0;
    }
    }
    cout << "NO ANSWER!" << endl;
    return 0;
    }

  • 0
    @ 2016-07-13 20:01:17

    坑,这题一个键可以对应多个值,像这样
    a->b
    a->c
    好多次才ac
    附代码:
    #include<iostream>
    #include<string>
    #include<cstdio>
    #include<map>
    #include<queue>
    #include<set>
    using namespace std;

    map<string,set<string> > g;
    map<string,int> d;
    string a,b;
    queue<string> q;

    int bfs()
    {
    q.push(a);
    for (d[a]=0;!q.empty();) {
    string s=q.front(); q.pop();
    if (s==b) return d[s];
    if (d[s]>10) return -1;
    for (map<string,set<string> >::iterator i=g.begin();i!=g.end();++i) {
    string sub=i->first;
    for (int j=0;j<s.size();++j) {
    if (s.substr(j,sub.size())==sub) {
    for (set<string>::iterator it=i->second.begin();it!=i->second.end();++it) {
    string v(s.substr(0,j)+*it+s.substr(j+sub.size(),s.size()-j-sub.size()));
    //cout<<v<<endl;
    if (d.find(v)==d.end()) {
    d[v]=d[s]+1;
    //cout<<d[v]<<"new state:"<<v<<endl;
    q.push(v);
    }
    }
    }
    }
    }
    }
    return -1;

    }

    int main()
    {
    //freopen("in.txt","r",stdin);
    //int j=0;
    //string s1("123456"),s2("www"),s3("12");
    //cout<<s1.substr(0,j)+s2+s1.substr(j+s3.size(),s1.size()-j-s3.size());
    cin>>a>>b;
    string t,s;
    while (cin>>t) {
    //if (t.first==".") break;
    string s; cin>>s;
    g[t].insert(s);
    }
    int ans=bfs();
    if (ans==-1) cout<<"NO ANSWER!";
    else cout<<ans;
    return 0;
    }

  • 0
    @ 2016-03-23 07:26:42

    include <iostream> include <cstring> include <map> include <queue> include <algorithm>

    using namespace std;
    string f[21], t[21], a, b;
    map<string, int> ff;
    queue<string> q;
    int tt = 1;
    void bfs(string x)
    {
    while(!q.empty()) {
    string x = q.front();
    if(x == b)
    return ;
    if(ff[x] >= 11) {
    q.pop();
    continue;
    }
    for(int i = 1; i < tt; i++) {
    int p = x.find(f[i]);
    while(p < x.size()) {
    string k = "";
    k += x.substr(0, p), k += t[i];
    k += x.substr(p + f[i].size(), x.size() - p - f[i].size());
    if(ff[k] == 0 || ff[x] + 1 < ff[k])
    ff[k] = ff[x] + 1, q.push(k);
    p = x.find(f[i], p + 1);
    }
    }
    q.pop();
    }
    }
    int main() {
    string x, y;
    cin >> a >> b;
    while(cin >> x >> y)
    if(x != y)
    f[tt] = x, t[tt++] = y;
    q.push(a), ff[a] = 1;
    bfs(a);
    if(ff[b] == 0)
    cout << "NO ANSWER!" << endl;
    else
    cout << ff[b] - 1 << endl;
    return 0;
    }
    某些小人觉得我不会这么慷慨大方,所以,小人去shi!!!

  • 0
    @ 2016-03-23 07:24:54

    记录信息
    评测状态 Accepted
    题目 P1124 字串变换
    递交时间 2016-03-21 07:45:29
    代码语言 C++
    评测机 ShadowShore
    消耗时间 279 ms
    消耗内存 1532 KiB
    评测时间 2016-03-21 07:45:30

    评测结果
    编译成功

    foo.cpp: In function 'void bfs(std::string)':
    foo.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(p < x.size()) {
    ^

    测试数据 #0: Accepted, time = 15 ms, mem = 576 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 576 KiB, score = 10

    测试数据 #2: Accepted, time = 0 ms, mem = 580 KiB, score = 10

    测试数据 #3: Accepted, time = 46 ms, mem = 980 KiB, score = 10

    测试数据 #4: Accepted, time = 218 ms, mem = 1532 KiB, score = 10

    Accepted, time = 279 ms, mem = 1532 KiB, score = 50

    代码

    include <iostream>

    include <cstring>

    include <map>

    include <queue>

    include <algorithm>

    using namespace std;
    string f[21], t[21], a, b;
    map<string, int> ff;
    queue<string> q;
    int tt = 1;
    void bfs(string x)
    {
    while(!q.empty()) {
    string x = q.front();
    if(x == b)
    return ;
    if(ff[x] >= 11) {
    q.pop();
    continue;
    }
    for(int i = 1; i < tt; i++) {
    int p = x.find(f[i]);
    while(p < x.size()) {
    string k = "";
    k += x.substr(0, p), k += t[i];
    k += x.substr(p + f[i].size(), x.size() - p - f[i].size());
    if(ff[k] == 0 || ff[x] + 1 < ff[k])
    ff[k] = ff[x] + 1, q.push(k);
    p = x.find(f[i], p + 1);
    }
    }
    q.pop();
    }
    }
    int main() {
    string x, y;
    cin >> a >> b;
    while(cin >> x >> y)
    if(x != y)
    f[tt] = x, t[tt++] = y;
    q.push(a), ff[a] = 1;
    bfs(a);
    if(ff[b] == 0)
    cout << "NO ANSWER!" << endl;
    else
    cout << ff[b] - 1 << endl;
    return 0;
    }

  • 0
    @ 2015-10-31 16:27:46

    哎,提交了3次。前两次错竟然是忘了把freopen注释掉,哎,郁闷啊。
    代码

    #include<cstring>
    #include<cstdio>
    #include<cstdlib>
    #include<iostream>
    using namespace std;
    struct node
    {
    char s[30];
    int dep;
    } list1[5010],list2[5010];
    char a[7][30],b[7][30];
    int n;
    bool check(char *s1,char *s2)
    {
    if (strlen(s1)!=strlen(s2)) return false;
    for (int i=0;i<strlen(s1);i++)
    if (s1[i]!=s2[i]) return false;
    return true;
    }
    bool pan1(char *s,int i,int x)
    {
    for (int j=i;j<i+strlen(a[x]);j++)
    if (s[j]!=a[x][j-i]) return false;
    return true;
    }
    bool pan2(char *s,int i,int x)
    {
    for (int j=i;j<i+strlen(b[x]);j++)
    if (s[j]!=b[x][j-i]) return false;
    return true;
    }
    void bfs()
    {
    int head1,tail1,head2,tail2,k;
    head1=tail1=head2=tail2=1;
    while (head1<=tail1 && head2<=tail2)
    {
    if (list1[head1].dep+list2[head2].dep>10)
    {
    printf("NO ANSWER!\n");
    return ;
    }
    for (int i=0;i<strlen(list1[head1].s);i++)
    for (int j=1;j<=n;j++)
    if (pan1(list1[head1].s,i,j))
    {
    tail1++;
    for (k=0;k<i;k++) list1[tail1].s[k]=list1[head1].s[k];
    for (int l=0;l<strlen(b[j]);l++,k++) list1[tail1].s[k]=b[j][l];
    for (int l=i+strlen(a[j]);l<=strlen(list1[head1].s);l++,k++)
    list1[tail1].s[k]=list1[head1].s[l];
    list1[tail1].s[k]='\0';
    list1[tail1].dep=list1[head1].dep+1;
    for (k=1;k<=tail1;k++)
    if (check(list1[tail1].s,list2[k].s))
    {
    printf("%d\n",list1[tail1].dep+list2[k].dep);
    return ;
    }
    }

    for (int i=0;i<strlen(list2[head2].s);i++)
    for (int j=1;j<=n;j++)
    if (pan2(list2[head2].s,i,j))
    {
    tail2++;
    for (k=0;k<i;k++) list2[tail2].s[k]=list2[head2].s[k];
    for (int l=0;l<strlen(a[j]);l++,k++) list2[tail2].s[k]=a[j][l];
    for (int l=i+strlen(b[j]);l<=strlen(list2[head2].s);l++,k++)
    list2[tail2].s[k]=list2[head2].s[l];
    list2[tail2].s[k]='\0';
    list2[tail2].dep=list2[head2].dep+1;
    for (k=1;k<=tail1;k++)
    if (check(list1[k].s,list2[tail2].s))
    {
    printf("%d\n",list1[k].dep+list2[tail2].dep);
    return ;
    }
    }
    head1++; head2++;
    }
    printf("NO ANSWER!\n");
    }
    int main()
    {
    //freopen("string.in","r",stdin);
    //freopen("string.out","w",stdout);
    scanf("%s%s",list1[1].s,list2[1].s);
    n=1;
    while (scanf("%s%s",a[n],b[n])!=EOF) n++;
    n--;
    list1[1].dep=list2[1].dep=0;
    bfs();
    return 0;
    }

  • 0
    @ 2015-09-20 20:27:52

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    #include<vector>
    #include<queue>
    #include<set>
    using namespace std;
    const int MAXN = 50;

    int n = 1, len1[MAXN], len2[MAXN];
    char list1[MAXN][MAXN], list2[MAXN][MAXN];
    vector<char> v;
    set<string> st;

    struct Status{
    int dep;

    char s[100];

    }first1, first2;

    queue<Status> q;

    bool check(Status a, Status b){
    if(strlen(a.s) != strlen(b.s))
    return 0;

    for(int i=0; i<strlen(a.s); i++)
    if(a.s[i] != b.s[i])
    return 0;
    return 1;
    }

    void clear(Status &now){
    for(int i=0; i<50; i++)
    now.s[i] = '\0';
    }

    void check(Status tmp, int a, int b){
    //int bri = strlen(tmp.s);
    //int tot = min(a+len1[b], bri);
    for(int i=a; i<a+len1[b]; i++)
    if(list1[b][i-a] != tmp.s[i])
    return;
    v.clear();
    Status now;
    clear(now);
    for(int i=0; i<a; i++)
    v.push_back(tmp.s[i]);
    for(int i=0; i<len2[b]; i++)
    v.push_back(list2[b][i]);
    for(int i=a+len1[b]; i<strlen(tmp.s); i++)
    v.push_back(tmp.s[i]);
    for(int i=0; i<v.size(); i++)
    now.s[i] = v[i];
    now.dep = tmp.dep + 1;
    if(strlen(now.s) > 20)
    return;
    if(!st.count(now.s)){
    q.push(now);
    st.insert(now.s);
    }
    }

    void bfs(){
    q.push(first1);
    while(!q.empty()){
    Status now = q.front();
    if(now.dep > 10){
    printf("NO ANSWER!");
    break;
    }
    if(check(now, first2)){
    printf("%d", now.dep);
    break;
    }
    q.pop();
    for(int i=0; i<strlen(now.s); i++)
    for(int j=1; j<=n; j++)
    check(now, i, j);
    if(q.empty())
    printf("NO ANSWER!");

    }
    }

    int main()
    {
    FILE *fin = fopen("in.txt", "r");
    fscanf(fin, "%s%s", first1.s, first2.s);
    while(fscanf(fin, "%s%s", list1[n], list2[n]) != EOF){
    len1[n] = strlen(list1[n]);
    len2[n] = strlen(list2[n]);
    n++;
    }
    n--;

    bfs();
    return 0;
    }
    BFS + set判重

  • 0
    @ 2015-07-16 16:27:32

    Block code

    #include <iostream>
    #include <cstring>
    #include <map>
    #include <queue>
    #include <algorithm>
    using namespace std;
    string f[21], t[21], a, b;
    map<string, int> ff;
    queue<string> q;
    int tt = 1;
    void bfs(string x)
    {
    while(!q.empty()) {
    string x = q.front();
    if(x == b)
    return ;
    if(ff[x] >= 11) {
    q.pop();
    continue;
    }
    for(int i = 1; i < tt; i++) {
    int p = x.find(f[i]);
    while(p < x.size()) {
    string k = "";
    k += x.substr(0, p), k += t[i];
    k += x.substr(p + f[i].size(), x.size() - p - f[i].size());
    if(ff[k] == 0 || ff[x] + 1 < ff[k])
    ff[k] = ff[x] + 1, q.push(k);
    p = x.find(f[i], p + 1);
    }
    }
    q.pop();
    }
    }
    int main() {
    string x, y;
    cin >> a >> b;
    while(cin >> x >> y)
    if(x != y)
    f[tt] = x, t[tt++] = y;
    q.push(a), ff[a] = 1;
    bfs(a);
    if(ff[b] == 0)
    cout << "NO ANSWER!" << endl;
    else
    cout << ff[b] - 1 << endl;
    return 0;
    }

    49行精简代码

  • 0
    @ 2014-11-05 15:02:24

    const prime:array[1..20] of longint=(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71);
    type info=record
    dep:longint;
    str:string;
    end;

    var
    u:info;
    d1,d2:array[0..100000] of string;
    i,j,head,tail,tot,dep,v,k:longint;
    queue:array[0..100000] of info;
    s,s1,s2,ts,tts:string;
    f:array[0..10000] of longint;
    hash:array[-100000000..100000000] of boolean;
    function check(str:string):boolean;
    var
    h:int64;
    i:longint;
    begin
    h:=0;

    for i:=1 to length(str) do
    begin
    h:=((h+ (ord(str[i])-48)*i*i*prime[i]));
    if (h>10000000)or(h<-10000000) then
    h:=h mod 99999989;
    end;
    h:=h mod 99999989;
    if hash[h] then
    exit(false) else
    begin
    hash[h]:=true;
    exit(true);
    end;
    end;

    procedure kmp(A,B:string);
    var
    i,j,m,n:longint;
    P:array[0..1000] of longint;
    begin
    m:=length(B);
    n:=length(A);
    P[1]:=0;
    j:=0;
    for i:=2 to n do
    begin
    while (j>0) and (A[j+1]<>A[i]) do
    j:=P[j];
    if A[j+1]=A[i] then
    j:=j+1;
    P[i]:=j;
    end;
    j:=0;
    v:=0;

    for i:=1 to m do
    begin
    while (j>0) and (A[j+1]<>B[i]) do
    j:=P[j];
    if A[j+1]=B[i] then j:=j+1;
    if j=n then
    begin
    inc(v);
    f[v]:=i-n+1;
    j:=P[j];
    end;
    end;
    end;

    begin
    readln(s);
    s1:=copy(s,1,pos(' ',s)-1);
    delete(s,1,pos(' ',s));
    s2:=s;

    tot:=0;
    while not eof do
    begin
    inc(tot);
    readln(s);
    d1[tot]:=copy(s,1,pos(' ',s)-1);
    delete(s,1,pos(' ',s));
    d2[tot]:=s;
    end;

    head:=1;
    tail:=1;
    queue[1].str:=s1;
    queue[1].dep:=0;
    while head<=tail do
    begin
    u:=queue[head];
    dep:=queue[head].dep;
    inc(head);
    if dep>10 then
    break;

    for j:=1 to tot do
    begin

    kmp(d1[j],u.str);

    if v>0 then
    begin
    for k:=1 to v do
    begin
    ts:=u.str;
    tts:=copy(ts,1,f[k]-1);
    delete(ts,1,f[k]+length(d1[j])-1);
    tts:=tts+d2[j]+ts;
    if check(tts) then
    begin
    inc(tail);
    queue[tail].str:=tts;
    queue[tail].dep:=dep+1;
    if tts=s2 then
    begin
    writeln(queue[tail].dep);
    halt;
    end;
    end;
    end;
    end;
    end;
    end;
    writeln('NO ANSWER!');
    end.

    KMP+hash+bfs

  • 0
    @ 2014-10-02 11:40:36

    program p1124;
    var
    a:array[1..600000]of longint;
    x,y,b:array[1..700000]of string[20];
    s,s1:string;
    i,j,n,he,ti,k:longint;
    begin

    readln(s);
    b[1]:=copy(s,1,pos(' ',s)-1);delete(s,1,pos(' ',s));s1:=s;
    while not eof do
    begin
    inc(n);
    readln(s);
    x[n]:=copy(s,1,pos(' ',s)-1);delete(s,1,pos(' ',s));y[n]:=s;
    end;
    he:=0;ti:=1;
    while he<=ti do
    begin
    inc(he);
    if b[he]=s1 then begin writeln(a[he]);halt;end;
    if a[he]>10 then begin writeln('NO ANSWER!');halt;end;
    for i:=1 to n do if pos(x[i],b[he])>0 then begin
    inc(ti);a[ti]:=a[he]+1;
    b[ti]:=b[he];insert(y[i],b[ti],pos(x[i],b[ti]));
    delete(b[ti],pos(x[i],b[ti]),length(x[i]));
    s:=b[he];k:=pos(x[i],s);
    delete(s,pos(x[i],s),length(x[i]));
    if pos(x[i],s)>0 then
    begin
    inc(ti);
    a[ti]:=a[he]+1;b[ti]:=s;
    insert(y[i],b[ti],pos(x[i],b[ti]));
    delete(b[ti],pos(x[i],b[ti]),length(x[i]));
    insert(x[i],b[ti],k);
    end;
    end;
    end;
    end.
    纯bfs,不加任何优化,AC

  • 0
    @ 2014-08-20 15:03:23

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    using namespace std;
    struct node
    {
    char s[30];
    int d;
    }l1[5010],l2[5010];
    main()
    {
    char a[7][30],b[7][30];
    int n=1,h1=1,t1=1,h2=1,t2=1,i,j,k,l;
    cin>>l1[1].s>>l2[1].s;
    while(scanf("%s%s",a[n],b[n])!=EOF)
    n++;
    n--;
    l1[1].d=l2[1].d=0;
    while(h1<=t1&&h2<=t2)
    {
    if(l1[h1].d+l2[h2].d>10)
    {
    cout<<"NO ANSWER!";
    return 0;
    }
    for(i=0;i<strlen(l1[h1].s);i++)
    for(j=1;j<=n;j++)
    if(strncmp(l1[h1].s+i,a[j],strlen(a[j]))==0)
    {
    t1++;
    for(k=0;k<i;k++)
    l1[t1].s[k]=l1[h1].s[k];
    for(l=0;l<strlen(b[j]);l++,k++)
    l1[t1].s[k]=b[j][l];
    for(l=i+strlen(a[j]);l<=strlen(l1[h1].s);l++,k++)
    l1[t1].s[k]=l1[h1].s[l];
    l1[t1].s[k]='\0';
    l1[t1].d=l1[h1].d+1;
    for(k=1;k<=t1;k++)
    if(strcmp(l1[t1].s,l2[k].s)==0)
    {
    cout<<l1[t1].d+l2[k].d;
    return 0;
    }
    }
    for(i=0;i<strlen(l2[h2].s);i++)
    for(j=1;j<=n;j++)
    if(strncmp(l2[h2].s+i,b[j],strlen(b[j]))==0)
    {
    t2++;
    for(k=0;k<i;k++)
    l2[t2].s[k]=l2[h2].s[k];
    for(l=0;l<strlen(a[j]);l++,k++)
    l2[t2].s[k]=a[j][l];
    for(l=i+strlen(b[j]);l<=strlen(l2[h2].s);l++,k++)
    l2[t2].s[k]=l2[h2].s[l];
    l2[t2].s[k]='\0';
    l2[t2].d=l2[h2].d+1;
    for(k=1;k<=t1;k++)
    if(strcmp(l1[k].s,l2[t2].s)==0)
    {
    cout<<l1[k].d+l2[t2].d;
    return 0;
    }
    }
    h1++;
    h2++;
    }
    cout<<"NO ANSWER!";
    }

  • 0
    @ 2014-05-30 21:16:13

    #code
    #include <iostream>
    #include <string>
    #include <map>
    #include <queue>
    #include <algorithm>
    #include <vector>
    using namespace std;
    using namespace __gnu_cxx;
    string start,end;
    vector<string> w1,w2;
    int findstr();
    int main(int argc, char** argv) {
    cin>>start>>end;
    string t1,t2;
    while(cin>>t1>>t2)
    {
    w1.push_back(t1);
    w2.push_back(t2);
    }
    int bfs();
    int q=bfs();
    if(q==-1) cout<<"NO ANSWER!"<<endl;
    else cout<<q<<endl;
    return 0;
    }
    int bfs()
    {
    map<string,int> l;
    l[start]=0;
    queue<string> q;
    q.push(start);
    while(!q.empty())
    {string n=q.front();
    for(int i=0;i!=w1.size();++i)
    {int k=0;
    while(k<n.size())
    {
    int p=n.find(w1[i].c_str(),k);
    k+=w1[i].size();
    if(p==string::npos) break;
    string n1;
    for(int j=0;j<p;++j)
    n1.push_back(n[j]);
    for(int j=0;j<w2[i].size();++j)
    n1.push_back(w2[i][j]);
    for(int j=p+w1[i].size();j<n.size();++j)
    n1.push_back(n[j]);
    if(l.count(n1)) continue;
    else
    l.insert(pair<string,int>(n1,l[n]+1));
    if(n1==end) return l[n1];
    if(l[n1]>10) return -1;
    q.push(n1);
    }
    }
    q.pop();
    }
    return -1;
    }
    纯STL实现......
    注意这么几点:
    有可能出现
    abaaaba abcdaba
    a b
    b d
    d e
    e f
    f g
    g c
    这样的数据
    bfs一定要判重
    最后要用一句 return-1;兜底防止无解情况
    只有59行哦

  • 0
    @ 2014-01-12 19:05:13

    61行单向BFS+hash,快被这题玩死了

  • 0
    @ 2013-08-18 23:26:43

    测试数据 #0: Accepted, time = 0 ms, mem = 5760 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 5760 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 5760 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 5760 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 5764 KiB, score = 10
    Accepted, time = 0 ms, mem = 5764 KiB, score = 50

    看代码:
    var q:array[1..2,1..10000] of string;{正反向队列}
    r:array[1..6,1..2] of string;{转换规则}
    step:array[1..2,1..1000] of integer;{答案计数}
    a,b:string; {初始状态和目标状态}
    h,t:array[1..2] of integer;{两个队列指针}
    n,change_number:integer;{规则数,转换结果数}
    change_list:array[1..20] of string;
    step_now:shortint;{现行步数}
    function change(var s:string;a,b:string):boolean;{转换}
    var p,p_t:longint;
    t:string;
    begin
    change_number:=0;
    p:=pos(a,s);
    while p<>0 do
    begin
    t:=s;
    delete(t,p,length(a));
    insert(b,t,p);
    inc(change_number);
    change_list[change_number]:=t;
    p_t:=pos(a,copy(s,p+1,length(s)));
    if p_t=0 then exit(true);
    inc(p,p_t);
    end;
    if (p=0)and(change_number=0) then exit(false);
    exit(true);
    end;
    procedure add(j{队列号},ste{步数}:shortint;x:string);
    begin
    inc(t[j]);
    step[j,t[j]]:=ste;
    q[j,t[j]]:=x;
    end;
    procedure del(j:shortint;var ste:shortint;var s:string);
    begin
    inc(h[j]);
    s:=q[j,h[j]];
    ste:=step[j,h[j]];
    end;
    function find(j:shortint;s:string):boolean;
    var i:longint;
    begin
    for i:=1 to t[3-j] do{是否在逆向搜索队列中出现}
    if s=q[3-j,i] then
    begin
    writeln(step[3-j,i]+step_now+1);{输出解}
    halt;
    end;
    for i:=1 to t[j] do{是在同向队列重复出现}
    if s=q[j,i] then exit(true);
    exit(false);
    end;
    procedure init;{输入初始以及目标,还有规则}
    var i:integer;
    s:string;
    begin
    i:=0;
    fillchar(h,sizeof(h),0);
    fillchar(t,sizeof(t),0);
    readln(s);
    n:=pos(' ',s);
    a:=copy(s,1,n-1);
    b:=copy(s,n+1,length(s));
    while not(eof) do
    begin
    inc(i);
    readln(s);
    n:=pos(' ',s);
    r[i,1]:=copy(s,1,n-1);
    r[i,2]:=copy(s,n+1,length(s));
    end;
    n:=i;
    add(1,0,a);
    add(2,0,b);
    end;
    procedure dbfs;{双向bfs}
    var i,j,k:integer;
    temp,str:string;
    begin
    while (t[1]>h[1])or(t[2]>h[2]) do
    for j:=1 to 2 do
    begin
    del(j,step_now,str);{取出队头元素}
    for i:=1 to n do{枚举每种转换规则}
    begin
    temp:=str;
    if change(temp,r[i,j],r[i,3-j]) then
    for k:=1 to change_number do
    if not find(j,change_list[k]) then
    add(j,step_now+1,change_list[k]);
    if (step[1,h[1]]>=10)and(step[2,h[2]]>=10) then exit;
    end;
    end;
    end;
    begin
    init;
    dbfs;
    writeln('NO ANSWER!');
    end.

  • 0
    @ 2012-10-16 21:35:01

    太棒了,不愧是经典题。

    通过一题多解,我不仅学习了hash表还学会了双向广搜。

  • 0
    @ 2012-08-08 10:52:01

    ├ 测试数据 01:答案正确... (333ms, 25804KB)

    ├ 测试数据 02:答案正确... (341ms, 25804KB)

    ├ 测试数据 03:答案正确... (142ms, 25804KB)

    ├ 测试数据 04:答案正确... (157ms, 25804KB)

    ├ 测试数据 05:答案正确... (118ms, 25804KB)

    ---|---|---|---|---|---|---|---|-

    Accepted / 100 / 1093ms / 25804KB

    双向BFS+天然剪枝

信息

ID
1124
难度
7
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
3886
已通过
784
通过率
20%
被复制
14
上传者