西宁网站建设公司,浩森宇特北京网站建设,短链接制作,wordpress主题 评论题目链接#xff1a;The Morning after Halloween 题目描述#xff1a; 给定一个二维矩阵#xff0c;图中有障碍物和字母#xff0c;你需要把小写字母移动到对应的大写字母位置#xff0c;不同的小写字母可以同时移动#xff08;上下左右四个方向或者保持不动 #xff0…题目链接The Morning after Halloween 题目描述 给定一个二维矩阵图中有障碍物和字母你需要把小写字母移动到对应的大写字母位置不同的小写字母可以同时移动上下左右四个方向或者保持不动 但是移动之后两个字母不能重合同时移动后不能是两个字母发生了位置的交换。 上图给出了一种情况即该情况下的四种合法移动。 同时题目保证任意一个2×22\times22×2的子区域中一定至少含有一个障碍物同时边界一定是障碍物。 题解 我们可以把每个矩阵的看成一个状态进行BFSBFSBFS但是这样状态的个数比较多。 由于题目保证了很小的区域有障碍这也就变相说明了题目可以到达的点并不会很多所以我们可以把每个可以经过的点进行编号然后记录字母落在点的编号的三元组缺少的字母用000来表示这意味着点的编号需要从111开始然后将三元组看成是状态而每一次移动看成是一条边这样我们只需要进行BFSBFSBFS即可找到目标状态的最少移动次数在移动的时候我们需要判断是否违反规则例如移动后两个字母在同一个位置或者移动导致两个相邻的字母发生的交换。由于本题的目标状态也是已知的那么我们可以使用双向BFSBFSBFS也就是从目标状态和初始状态同时进行BFSBFSBFS当在中间的某个状态相遇的时候就意味着找到了最少花费在代码中我们只需要两个队列就可以实现双向BFSBFSBFS一个放入初始状态进行搜索一个放入目标状态进行搜索。 为什么需要双向BFSBFSBFS双向BFSBFSBFS通常情况下能够让时间复杂度下降。原理实际上是因为每一次都选择含有较少的节点进行扩展这样能一定程度上节省时间。 双向BFSBFSBFS的代码应该是每次选择较小的队列进行扩展而不是轮流进行扩展如果是轮流进行扩展那么实际上和单向BFSBFSBFS没有太大的差别。 代码
#include bits/stdc.hconst int DIRECTION_NUM 5;
const int MAXH 16 1;
const int MAXW 16 1;
const int MAX_NODE MAXH * MAXW;using namespace std;int w, h, n, nodeNum;
char g[MAXH][MAXW];
int dx[] {0, 1, -1, 0, 0};
int dy[] {0, 0, 0, 1, -1};
vectorint es[MAX_NODE];
int nodeId[MAXH][MAXW];
mapchar, int s, t;
int dis[MAX_NODE][MAX_NODE][MAX_NODE];
int inQ[MAX_NODE][MAX_NODE][MAX_NODE];struct State
{int a, b, c; //最多三个字母位置的结点编号State() {}State(int a, int b, int c) : a(a), b(b), c(c) {}State operator(mapchar, int rhs){a b c 0;auto iter rhs.begin();for (size_t i 0; i n; i) {if (i 0) { a iter-second; }else if (i 1) { b iter-second; }else if (i 2) { c iter-second; }iter;}return *this;}
}st, ed;void buildGraph()
{nodeNum 1;s.clear();t.clear();for (int i 0; i MAX_NODE; i) { es[i].resize(0); }for (int i 0; i h; i) {for (int j 0; j w; j) {if (g[i][j] #) { continue; }nodeId[i][j] nodeNum;if (islower(g[i][j])) {s[g[i][j]] nodeId[i][j];} else if (isupper(g[i][j])) {t[g[i][j]] nodeId[i][j];}}}st s;ed t;es[0].push_back(0);for (int i 0; i h; i) {for (int j 0; j w; j) {if (g[i][j] #) { continue; }for (int k 0; k DIRECTION_NUM; k) {int nx i dx[k];int ny j dy[k];if (g[nx][ny] #) { continue; }es[nodeId[i][j]].push_back(nodeId[nx][ny]);}}}
}bool conflict(int newA, int newB, int a, int b) { return (newA newB newA ! 0) || (newA b newB a newA ! 0 newB ! 0); }int bfs(queueState q, int nowQ)
{int size q.size();int a, b, c;while(size--) {State now q.front();q.pop();a now.a, b now.b, c now.c;for (auto newA : es[a]) {for (auto newB : es[b]) {if (conflict(newA, newB, a, b)) { continue; }for (auto newC : es[c]) {if (conflict(newA, newC, a, c) || conflict(newB, newC, b, c)) { continue; }if (inQ[newA][newB][newC] nowQ) { continue; }if (inQ[newA][newB][newC] 3 - nowQ) { // 在另一个队列中cout dis[newA][newB][newC] dis[a][b][c] 1 endl;return 0;}dis[newA][newB][newC] dis[a][b][c] 1;inQ[newA][newB][newC] nowQ;q.push({newA, newB, newC});}}}}return -1;
}void dBfs()
{queueState qs;queueState qt;memset(inQ, 0, sizeof(inQ));qs.push(st);qt.push(ed);dis[st.a][st.b][st.c] 0;inQ[st.a][st.b][st.c] 1;dis[ed.a][ed.b][ed.c] 0;inQ[ed.a][ed.b][ed.c] 2;while (!qs.empty() !qt.empty()) {if (qs.size() qt.size()) { // 优先选择队列短的队列进行bfsif(bfs(qs, 1) ! -1) { return; }}else {if(bfs(qt, 2) ! -1) { return; };}}
}int main()
{ios::sync_with_stdio(false);while(cin w h n) {if (w 0 h 0 n 0) { break; }cin.get(); //读取末尾的换行for (int i 0; i h; i) { cin.getline(g[i], MAXW); } // cin.getline读取的数据末尾没有\n, cin.getline会保证末尾有结束符0所以最多读取MAXW-1个有效字符buildGraph();dBfs();}return 0;
}
