题意:现在给你一个被人走过的 m * n 迷宫,每一个位置用 # / 1 / 0 标记。标记为 #,表示障碍物,没有人能通过;标记为 1,表示这个格子有人走过;标记为 0,表示这个格子没人走过。迷宫的起点为 (1, 1),终点为 (m, n),从起点往终点只能向右或下方走。假设每一个人走出迷宫的路线均不相同,请问至少有多少人走过了迷宫。
输入:第一行为两个整数 m,n;
接下来 m 行,每行 n 个字符,同一行的字符串之间没有间隔,表示迷宫的状态。
输出:最少走过迷宫的人数。
样例输入:
5 8
111#00#0
011110#0
011#111#
011#1011
01111111
样例输出:
11
数据规模与约定: 对于 100 %数据,1≤m,n≤104,数据保证起点和终点的标记一定是 1。
时间限制:2.000s,内存限制:128MB
丑陋代码:
#include <bits/stdc++.h>
using namespace std;
int n, m, k, ans, dx[2] = {0, 1}, dy[2] = {1, 0};
bool Map[10010][10010], v[10010][10010]; string c;
void dfs (int x, int y)
{
if (x == m && y == n)
{
ans++;
return;
}
else
{
for (int i = 0; i < 2; i++)
if (x + dx[i] <= m && y + dy[i] <= n && Map[x + dx[i]][y + dy[i]] == 1 && v[x + dx[i]][y + dy[i]] == 0)
{
v[x][y] = 1;
k++;
dfs (x + dx[i], y + dy[i]);
v[x][y] = 0;
k--;
}
}
}
int main ( )
{
cin >> m >> n;
for (int i = 1; i <= m; i++)
{
cin >> c;
for (int j = 1; j <= n; j++)
{
if (c[j - 1] == '1') Map[i][j] = 1;
else Map[i][j] = 0;
}
}
//我觉得'0','#'应该都是一样的,一个是不能走,一个是没人走,不都一个意思
dfs (1, 1);
cout << ans << '\n';
return 0;
}
求问为什么运行错误,不胜感激!