我是一名学生,主要学习C++。我知道我的错误可能会让某些人感到沮丧,但请知道我渴望改进,我将不胜感激任何诚实的反馈。
我正在尝试解决一个似乎涉及深度优先搜索的算法问题。 为了简要解释问题的内容,最初输入了一个二维数组(具有行数和列数),仅由“0”和“1”组成。数组本身代表一个迷宫,我只能沿着 1 继续的路径走。(0 代表挡住我路径的墙。)
例如
4 6
101111
101010
101011
111011
这样,我从左上角(0,0)开始,我必须到达路径结束的右下角(4, 6)。保证每个迷宫至少有一条路径可以让我走到尽头,我的工作是搜索在最佳路径中我必须通过的最少数量的“1”块。 (你可以向所有方向移动,NESW,但你不能沿对角线移动。) 我假设解决必须使用 DFS 来完成,这里是代码:
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
int n, m;
vector<string>grid; // I used vector to store the 2d array
int dfs(int x, int y, int count, map<pair<int, int>, bool>searchPath) { // Recursive function to perform DFS.
vector<int>num; //This vector will store 4 numbers in each cycle, where these are numbers of 1 blocks that will be passed for 4 direction: N, S, E, and W.
bool atLeast = false; // boolean to check if at least one of 4 directions meets the condition
count++;
//searchPath is a map to indicate that the path was already taken that it can't be passed again. This prevents the code from getting stuck in infinite loop.
if (grid[x - 1][y] == '1' && !searchPath[make_pair(x - 1, y)]) { //check if the block at the specific direction to me is not 0 and the block was already passed before.
map<pair<int, int>, bool>searchPath2(searchPath);
// copy of the map, and this will be used as an argument for the next recursive loop.
atLeast = 1;
searchPath2[make_pair(x - 1, y)] = true; //indicate this block is now taken
int val1 = dfs(x - 1, y, count, searchPath2); //Run the subsequent recursive loop where now I'm at the block that was at my left side.
if (val1 != 0) { //If the path starting from that block seems to have a solution, store it to the vector, num where I will find the minimum element and return it at the end of the function.
num.push_back(val1); //store the number of 1 blocks that will be passed if I make a decision to go west
}
}
if (grid[x + 1][y] == '1' && !searchPath[make_pair(x + 1, y)]) {
atLeast = 1;
if (x + 1 == n && y == m) {
return count;
}
map<pair<int, int>, bool>searchPath2(searchPath);
searchPath2[make_pair(x - 1, y)] = true;
int val2 = dfs(x + 1, y, count, searchPath2);
if (val2 != 0) {
num.push_back(val2);
}
}
if (grid[x][y - 1] == '1' && !searchPath[make_pair(x, y - 1)]) {
atLeast = 1;
map<pair<int, int>, bool>searchPath2(searchPath);
searchPath2[make_pair(x, y - 1)] = true;
int val3 = dfs(x, y - 1, count, searchPath2);
if (val3 != 0) {
num.push_back(val3);
}
}
if (grid[x][y + 1] == '1' && !searchPath[make_pair(x, y + 1)]) {
atLeast = 1;
if (x == n && y + 1 == m) {
return count;
}
map<pair<int, int>, bool>searchPath2(searchPath);
searchPath2[make_pair(x, y + 1)] = true;
int val4 = dfs(x, y + 1, count, searchPath2);
if (val4 != 0) {
num.push_back(val4);
}
}
if (!atLeast) {
return 0;
}
else {
return *min_element(num.begin(), num.end());
}
}
int main(void) {
cin >> n >> m;
grid.resize(n);
for (auto &iter : grid) {
cin >> iter;
}
map<pair<int, int>, bool>searchPath;
searchPath[make_pair(0, 0)] = true;
cout << dfs(0, 0, 0, searchPath);
return 0;
}
代码似乎有运行时错误...这是错误标志:
/tmp/program/run.sh: line 1: 178 Segmentation fault ./prog Command exited with non-zero status 139
请帮我找出问题出在哪一行。 :(