算法提高之搜索：多源BFS、最小步数模型、双端队列广搜

1、矩阵距离2、魔板3、电路维修 1、矩阵距离

#include #include #include #define x first#define y secondusing namespace std;typedef pair PII;const int N = 1010, M = N * N;int n, m;char g[N][N];PII q[M];int dist[N][N];void bfs(){ int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; memset(dist, -1, sizeof dist); int hh = 0, tt = -1; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) if (g[i][j] == '1') { dist[i][j] = 0; q[ ++ tt] = {i, j}; } while (hh <= tt) { auto t = q[hh ++ ]; for (int i = 0; i < 4; i ++ ) { int a = t.x + dx[i], b = t.y + dy[i]; if (a < 1 || a > n || b < 1 || b > m) continue; if (dist[a][b] != -1) continue; dist[a][b] = dist[t.x][t.y] + 1; q[ ++ tt] = {a, b}; } }}int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) scanf("%s", g[i] + 1); bfs(); for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= m; j ++ ) printf("%d ", dist[i][j]); puts(""); } return 0;}

#include #include #include #include #include using namespace std;//涉及到get和set 使用char方便操作char g[2][4];unordered_map> pre;unordered_map dist;void set(string state) { for (int i = 0; i < 4; i ++ ) g[0][i] = state[i]; for (int i = 7, j = 0; j < 4; i --, j ++ ) g[1][j] = state[i];}string get(){ string res; for (int i = 0; i < 4; i ++ ) res += g[0][i]; for (int i = 3; i >= 0; i -- ) res += g[1][i]; return res;}string move0(string state){ set(state); for (int i = 0; i < 4; i ++ ) swap(g[0][i], g[1][i]); return get();} string move1(string state){ set(state); int v0 = g[0][3], v1 = g[1][3]; for (int i = 3; i >= 0; i -- ) { g[0][i] = g[0][i - 1]; g[1][i] = g[1][i - 1]; } g[0][0] = v0, g[1][0] = v1; return get();}string move2(string state){ set(state); char v = g[0][1]; g[0][1] = g[1][1]; g[1][1] = g[1][2]; g[1][2] = g[0][2]; g[0][2] = v; return get();}int bfs(string start, string end){ if (start == end) return 0; queue q; q.push(start); dist[start] = 0; while (!q.empty()) { auto t = q.front(); q.pop(); string m[3]; m[0] = move0(t); m[1] = move1(t); m[2] = move2(t); for (int i = 0; i < 3; i ++ ) if (!dist.count(m[i])) { dist[m[i]] = dist[t] + 1; pre[m[i]] = {'A' + i, t}; q.push(m[i]); if (m[i] == end) return dist[end]; } } return -1;}int main(){ int x; string start, end; for (int i = 0; i < 8; i ++ ) { cin >> x; end += char(x + '0'); } for (int i = 1; i <= 8; i ++ ) start += char('0' + i); int step = bfs(start, end); cout << step << endl; string res; while (end != start) { res += pre[end].first; end = pre[end].second; } reverse(res.begin(), res.end()); if (step > 0) cout << res << endl; return 0;}

dijkstra可以做

点的坐标



字符的坐标


int bfs()
{
deque q;
}

#include #include #include #include #define x first#define y secondusing namespace std;typedef pair PII;const int N = 510, M = N * N;int n, m;char g[N][N];//因为是dijsktra算法//需要距离 和判重数组int dist[N][N];//判重数组是，防止使用一个点多次更新到其它点的距离//模仿dijsktrabool st[N][N];int bfs(){ memset(dist, 0x3f, sizeof dist); memset(st, 0, sizeof st); dist[0][0] = 0; deque q; q.push_back({0, 0}); //按字符坐标 得到格子中的字符 // \转义字符 需要打2个 char cs[] = "\/\/"; //周围的点 int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1}; //周围格子中的字符坐标 int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1}; while (q.size()) { PII t = q.front(); q.pop_front();//模仿在dijsktra中 扩展一个点到周围点的最小距离//出队时，这个点的dist是最小值 if (st[t.x][t.y]) continue; st[t.x][t.y] = true; for (int i = 0; i < 4; i ++ ) { int a = t.x + dx[i], b = t.y + dy[i]; //格点的长度比格子的长度多1. //格子的长度是(0,0)-(n-1,m-1) //格点是（0,0）-(n,m) if (a < 0 || a > n || b < 0 || b > m) continue;//格子中字符 int ca = t、x + ix[i], cb = t.y + iy[i]; //g[ca][cb]真实格子中的字符 cs[i] 以t这个点向a，b走，需要格子字符的走向 //相同 不加，不同则+1 int d = dist[t.x][t.y] + (g[ca][cb] != cs[i]); if (d