C++实现：画家在洪水中安全回家的最短时间求解

这是一个典型的图搜索问题，其中涉及到多步决策和状态转换。我们可以使用广度优先搜索（BFS）来解决这个问题，因为BFS可以找到从起点到终点的最短路径。 具体思路如下： 1. 定义状态：我们需要记录画家当前的位置、当前的时间步以及洪水蔓延的状态。 2. 初始状态：画家位于起始位置，时间为0，洪水尚未进一步蔓延。 3. 终止状态：画家到达住所位置。 4. 状态转换：画家可以向四个方向移动，同时洪水也可以向四个方向蔓延（但不包括岩石位置）。 5. BFS搜索：使用队列进行广度优先搜索，每次取出队列的一个状态，尝试所有可能的移动，生成新的状态，并将新状态加入队列。 以下是用C++实现的代码： ```cpp #include <iostream> #include <vector> #include <queue> #include <tuple> #include <unordered_set> using namespace std; // 四个方向的行列偏移量 const int dx[4] = {-1, 1, 0, 0}; const int dy[4] = {0, 0, -1, 1}; // 检查位置是否合法 bool isValid(int x, int y, int R, int C) { return x >= 0 && x < R && y >= 0 && y < C; } // BFS搜索函数 string bfs(vector<string>& map, int startX, int startY, int endX, int endY) { int R = map.size(); int C = map[0].size(); // 队列中存储 (画家x, 画家y, 时间步, 洪水地图) queue<tuple<int, int, int, vector<string>>> q; // 记录已访问的状态，防止重复搜索 unordered_set<string> visited; // 初始化起点状态 q.push({startX, startY, 0, map}); visited.insert(to_string(startX) + "," + to_string(startY) + "," + to_string(0) + "," + ""); for (string& row : map) { visited.insert(visited.back() + row); } while (!q.empty()) { auto [cx, cy, time, currMap] = q.front(); q.pop(); // 如果画家到达住所 if (cx == endX && cy == endY) { return to_string(time); } // 模拟洪水蔓延 vector<string> nextMap = currMap; for (int i = 0; i < R; ++i) { for (int j = 0; j < C; ++j) { if (currMap[i][j] == '.') { bool willFlood = false; for (int k = 0; k < 4; ++k) { int nx = i + dx[k]; int ny = j + dy[k]; if (isValid(nx, ny, R, C) && currMap[nx][ny] == '*') { willFlood = true; break; } } if (willFlood) { nextMap[i][j] = '*'; } } } } // 尝试四个方向移动 for (int k = 0; k < 4; ++k) { int nx = cx + dx[k]; int ny = cy + dy[k]; if (isValid(nx, ny, R, C) && nextMap[nx][ny] != 'X' && nextMap[nx][ny] != '*') { string newKey = to_string(nx) + "," + to_string(ny) + "," + to_string(time + 1) + ","; bool isValidState = true; for (int i = 0; i < R; ++i) { newKey += nextMap[i]; if (visited.find(newKey.substr(0, newKey.size() - C)) != visited.end()) { isValidState = false; break; } } if (isValidState && visited.find(newKey) == visited.end()) { q.push({nx, ny, time + 1, nextMap}); visited.insert(newKey); } } } } // 如果队列为空仍未找到路径，则无法安全回家 return "KAKTUS"; } int main() { int R, C; cin >> R >> C; vector<string> map(R); for (int i = 0; i < R; ++i) { cin >> map[i]; } int startX, startY, endX, endY; for (int i = 0; i < R; ++i) { for (int j = 0; j < C; ++j) { if (map[i][j] == 'S') { startX = i; startY = j; } else if (map[i][j] == 'D') { endX = i; endY = j; } } } cout << bfs(map, startX, startY, endX, endY) << endl; return 0; } ``` 逻辑点需要注意： 1. 状态表示：状态需要包括画家位置、时间和洪水地图，确保每个状态是唯一的。 2. 洪水蔓延模拟：在每一时间步，都需要根据当前地图模拟洪水蔓延。 3. 避免重复访问：使用哈希集合记录已访问的状态，避免重复搜索。 ######[AI写代码神器 | 1384点数解答 | 2025-03-16 17:33:49]