C++U5-06-广度优先搜索3

【算法分析】
可以以转弯次数为依据进行广搜，这样就是每一个方向都走到尽头。特别要注意的是当这个位置访问过，还是要继续要向这个方向走，因为后面可能有没有访问过的位置。

【参考代码】
#include<bits/stdc++.h>
using namespace std;

char MAP[109][109];
int dir[4][2] = { -1,0,0,1,1,0,0,-1 };
struct node {
    int x, y, step;
}l,r;
bool vis[109][109];
int main() {
    int n;
    cin >> n;
    int sx, sy, ex, ey;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            getchar();
            cin >> MAP[i][j];
        }
        for (int j = 1; j <= n; j++) {
            if (MAP[i][j] == 'A') sx = i, sy = j;
            else if (MAP[i][j] == 'B') ex = i, ey = j;
        }
    }
    queue<node> q;
    q.push({ sx,sy,0 });
    vis[sx][sy] = 1;
    while (q.size()) {
        r = q.front();
        q.pop();
        if (r.x == ex && r.y == ey) {
            cout << r.step - 1;
            break;
        }
        for (int i = 0; i < 4; i++) {
            for (int j = 1;; j++) {
                l.x = r.x + j * dir[i][0], l.y = r.y + j * dir[i][1], l.step = r.step + 1;
                if (l.x >= 1 && l.x <= n && l.y >= 1 && l.y <= n && MAP[l.x][l.y] != 'x' ) {
                    if (!vis[l.x][l.y]) {
                        vis[l.x][l.y] = 1;
                        q.push(l);
                    }
                }
                else break;
            }
        }
    }
    if (!vis[ex][ey]) cout << -1;
    return 0;
}

【算法分析】
从 start 字符串开始进行广搜，每次只变化一个字符。可以用 map 来记录达到某个字符串所需的最小次数。用 set 存储基因库，用于快速判断基因是否在基因库中。

【参考代码】
#include<bits/stdc++.h>
using namespace std;


int main() {
    string start, end;
    cin >> start >> end;
    int n;
    cin >> n;
    set<string> se;
    for (int i = 0; i < n; i++) {
        string a;
        cin >> a;
        se.insert(a);
    }
    map<string, int> mp;
    mp[start] = 0;
    queue<string> q;
    q.push(start);
    while (q.size()) {
        string r = q.front();
        q.pop();
        for (int i = 0; i < 8; i++) {
            string tem = r;
            tem[i] = 'A';
            if (!mp.count(tem) && se.count(tem)) {
                mp[tem] = mp[r] + 1;
                q.push(tem);
            }

            tem[i] = 'C';
            if (!mp.count(tem) && se.count(tem)) {
                mp[tem] = mp[r] + 1;
                q.push(tem);
            }

            tem[i] = 'G';
            if (!mp.count(tem) && se.count(tem)) {
                mp[tem] = mp[r] + 1;
                q.push(tem);
            }

            tem[i] = 'T';
            if (!mp.count(tem) && se.count(tem)) {
                mp[tem] = mp[r] + 1;
                q.push(tem);
            }
        }
    }
    if (mp.count(end)) cout << mp[end];
    else cout << -1;
    return 0;
}