我正在解决C ++挑战问题(迷宫)

问题

有一个由N X M大小的数组表示的迷宫。在迷宫中,1表示可移动的正方形,0表示不可移动的正方形,而2表示快捷方式。给定迷宫,编写一个从(1,1)开始的程序,查找移动到(N,M)时必须经过的最小空格数。从一个正方形移动到另一个正方形时,只能移动到相邻的正方形。此外,当您从一个正方形移至快捷方式时,您会立即移至相邻的正方形。也就是说,捷径是没有空间的。

输入

在第一行中,给出了两个整数N和M(2≤N,M≤100)。在接下来的N行中,将迷宫的M个正方形指定为0、1、2。仅在总是有可能移动到到达位置时才给出输入。

输出

打印第一行必须经过的最小空格数。

4 6                                   2 13
1 0 1 1 1 1                           1 0 1 1 2 0 1 1 2 0 1 1 1     
1 0 1 0 1 0                           1 1 1 0 1 1 1 0 1 1 1 0 1
1 0 1 0 1 1                           18
1 1 1 0 1 1 
15

这是我的代码。我不知道带有图形和向量的数组。

#include <iostream>
#include <stack>
#include <vector>
#include <cstdio>
#include <algorithm>

using std::cin;
using std::endl;
using std::cout;

std::stack<int> s;
std::vector<int> *graph;
bool *check;
int x, N, M, start;

void dfs()
{
s.push(start);
check[start] = true; 
printf("%d", start);

while(!s.empty()){
    int cur = s.top();
    s.pop();
    for(int i = 0; i < graph[cur].size(); i++){
        int next = graph[cur][i];
        if(check[next] == false){
            printf("%d", next);
            check[next] = true;
            s.push(cur);
            s.push(next);
            break;
        }
    }
}
}
int main()
{
cin >> N >> M;

for(int i = 0; i < N; i++){
    for(int j = 0; j < M; j++){
        cin >> x;
    }
    printf("\n");
}

graph = new std::vector<int>[N + 1][M];
check = new bool[N + 1];
std::fill(check, check + N + 1 + 1, false);

dfs();

return 0;
}
评论