【华为练习题】 闯迷宫（高级）

【华为练习题】 闯迷宫（高级）

题目

sun所在学校每年都要举行电脑节，今年电脑节有一个新的趣味比赛项目叫做闯迷宫。
sun的室友在帮电脑节设计迷宫，所以室友就请sun帮忙计算下走出迷宫的最少步数。
知道了最少步数就可以辅助控制比赛难度以及去掉一些没有路径到达终点的map。
比赛规则是：从原点（0,0）开始走到终点（n-1,n-1），只能上下左右4个方向走，只能在给定的矩阵里走。
运行时间限制: 10 Sec
内存限制: 128 MByte
输入:
输入有多组数据。

每组数据输入n（0

分析

用递归的方式找出所有路径，输出其中最短的路径长度。递归的每一步分别判断上下左右的4个位置是否可以进入，如果有位置可以进入，则从该位置开始下一步递归，递归的结束条件为进入到终点位置，或者上下左右4个位置都无法进入或已结束遍历。

解答

#include <iostream>
#include <vector>
using namespace std;

bool canVisit(const vector<int> &ways, int index){
for (auto begin = ways.begin(); begin != ways.end(); ++begin)
    {
if (*begin == index)
        {
return false;
        }
    }
return true;
}

bool findWay(const vector<vector<int> > &map, vector<int> ways, int n, int row, int col, int &min){
if (row == n - 1 && col == n - 1)
    {
if ((int)ways.size() - 1 < min)
        {
            min = ways.size() - 1;
        }
return true;
    }
bool flag1 = false, flag2 = false, flag3 = false, flag4 = false;
if (row < n - 1 && map[row+1][col] == 0 && canVisit(ways, (row + 1) * n + col))
    {
        ways.push_back((row + 1) * n + col);
        flag1 = findWay(map, ways, n, row + 1, col, min);
        ways.pop_back();
    }
if (col < n - 1 && map[row][col+1] == 0  && canVisit(ways, row  * n + col + 1))
    {
        ways.push_back(row * n + col + 1);
        flag2 = findWay(map, ways, n, row, col + 1, min);
        ways.pop_back();
    }
if (row > 0 && map[row-1][col] == 0  && canVisit(ways, (row - 1) * n + col))
    {
        ways.push_back((row - 1) * n + col);
        flag3 = findWay(map, ways, n, row - 1, col, min);
        ways.pop_back();
    }
if (col > 0 && map[row][col-1] == 0  && canVisit(ways, row  * n + col - 1))
    {
        ways.push_back(row * n + col - 1);
        flag4 = findWay(map, ways, n, row, col - 1, min);
        ways.pop_back();
    }
return flag1 || flag2 || flag3 || flag4;
}

int main(){
int n;
while (cin >> n)
    {
vector<int> ways , tmp(n);
vector<vector<int> > map(n, tmp);
for (int i = 0; i < n; i++)
        {
for (int j = 0; j < n; j++)
            {
cin >> map[i][j];
            }
        }
if (map[0][0] == 1 || map[n-1][n-1] == 1) cout << -1;
else
        {
            ways.push_back(0);
int min = n * n;
cout << (findWay(map,ways,n,0,0,min) ? min : -1) << endl;
        }
    }
return 0;
}