- 6 营救公主
- 2018-12-02 16:54:30 @
求大家帮忙想想是哪里漏了情况没考虑。
算法为递归:
走到右下角
{//每走一步路径长加一,每回退一步减一
如果走到墙则回到上一个路点
如果走到已经走过的点则回到上一个路点
如果走到右下角则判断时候是否比最小记录更近,更近则更新最小记录
当前路口向上走
当前路口向下走
当前路口向左走
当前路口向右走
}
走回左下角
{//每找到项链记录加一,每从项链点回退则记录减一
如果走到墙则回到上一个路点
如果走到已经走过的点则回到上一个路点
如果走到左上角则判断时候是否比最大项链记录更大,更大则更新最大记录
当前路口向上走
当前路口向下走
当前路口向左走
当前路口向右走
}
代码如下:
#include <iostream>
#include <vector>
using namespace std;
class graph
{
private:
vector<vector<char>> map;
vector<vector<int>> map_temp;//用于递归实时记录上一个路口以及项链位置的临时地图
int minRoad;
int maxNecklace;
int length, height;
void GoPath(int m, int n);
void ReturnPath(int m, int n);
public:
graph(int m,int n);
void Go() { GoPath(0,0); }
void Back() {
for (int i = 0; i < height; i++)
for (int j = 0; j < length; j++)
{
if (map[i][j] == '1')
map_temp[i][j] = 1;
else if (map[i][j] == '0')
map_temp[i][j] = 0;
else
map_temp[i][j] = 99;
}ReturnPath(height-1,length-1); }
int getGoMin() { return minRoad; }
int getMaxNeck() { return maxNecklace; }
};
graph::graph(int m, int n)
{
length = n;
height = m;
map.resize(height);
for (int i = 0; i < height; i++)
map[i].resize(length);
map_temp.resize(height);
for (int i = 0; i < height; i++)
map_temp[i].resize(length);
for (int i = 0; i < height; i++)
for (int j = 0; j < length; j++)
{
cin >> map[i][j];
}
for (int i = 0; i < height; i++)
for (int j = 0; j < length; j++)
{
if (map[i][j] == '1')
map_temp[i][j] = 1;
else if (map[i][j] == '0')
map_temp[i][j] = 0;
else
map_temp[i][j] = 99;
}
minRoad = 999;
maxNecklace = 0;
}
void graph::GoPath(int m, int n)
{
static int tempRoad = 0;
tempRoad++;
if (m < 0 || n < 0 || m >= height || n >= length)
{//超出地图
tempRoad--;
return;
}
if (map_temp[m][n] == 1 || map_temp[m][n] == 2)
{//撞墙回头,走过的地方回头
tempRoad--;
return;
}
if (m == height - 1 && n == length - 1)
{//走到公主
if (tempRoad < minRoad)
minRoad = tempRoad-1;
tempRoad--;
return;
}
map_temp[m][n] = 2;//2表示已经走过的路径,防止走回头路
GoPath(m, n + 1);//右走
GoPath(m + 1, n);//左走
GoPath(m, n - 1);//下走
GoPath(m - 1, n);//上走
map_temp[m][n] = 0;
tempRoad--;
}
void graph::ReturnPath(int m, int n)
{
static int tempNeck = 0;
if (m < 0 || n < 0 || m >= height || n >= length)
return;
if (map_temp[m][n] == 1 || map_temp[m][n] == 2 || map_temp[m][n] == 3)
return;//撞墙回头
if (m == 0 && n == 0)
{//到达目的地
if (maxNecklace < tempNeck)
maxNecklace = tempNeck;
return;
}
if (map_temp[m][n] == 99)//99表示项链
{
tempNeck++;
map_temp[m][n] = 3;//标记为3与2区分,如果从项链点回退,项链数量-1
}
else
map_temp[m][n] = 2;
ReturnPath(m, n + 1);
ReturnPath(m + 1, n);
ReturnPath(m, n - 1);
ReturnPath(m - 1, n);
if (map_temp[m][n] == 3)
tempNeck--;
map_temp[m][n] = 0;
}
int main()
{
int m, n;
cin >> m >> n;
graph G(m, n);
G.Go();
G.Back();
cout << G.getGoMin() << " " << G.getMaxNeck();
system("pause");
return 0;
}
0 条评论
目前还没有评论...
信息
- 难度
- 7
- 分类
- (无)
- 标签
- 递交数
- 209
- 已通过
- 39
- 通过率
- 19%
- 被复制
- 8
- 上传者