一个简单路径问题，求算法实现
给定固定大小20*20的棋盘，可以简单的认为是20*20的数组A，该数组记录了地形，
A[i,j] = 0 表示地形不可通过，棋子不可以经过
A[i,j] = 1 表示地形可以通过
已知棋子的起始点，问经过4步移动，会有几种路径，求算法实现，尽量不用递归。
求大家帮忙，谢谢。
举个例子：
00000000
00111100
00011100
00010000
00000000
00111000
00011100
00010000
00000000
00111100
00011100
00010000
00000000
00111100
00011100
00010000 算法实现，搜索，回溯
[解决办法]
有没说明白的地方，例如，棋子从a点走到b点再从b点走到a点，如此4步形成的路径可以吗？
[解决办法]
#include <cstdio>
#include <assert.h>
#include <vector>
#include <algorithm>
/**
* 计算4步路径所有可能
* @param map 二值地图，true表示通行，false表示障碍，原点在左上角
* @param map_width 地图宽度
* @param map_height 地图高度
* @param x0 初始位置横坐标
* @param y0 初始位置纵坐标
* @param routes 返回所有可能的路径
*/
void mapping(const bool * map,
int map_width, int map_height,
int x0, int y0,
std::vector<std::vector<std::pair<int, int> > > & routes)
{
assert(map != NULL); //map不可为空
assert(map_width > 0 && map_height > 0); //长宽不可为空
assert(x0 >= 0 && x0 < map_width); //初始点横坐标不可越界
assert(y0 >= 0 && y0 < map_height); //初始点纵坐标不可越界
assert(map[y0 * map_width + x0]); //初始点应属于可通行点
//上、左、下、右四个方向偏移
int x_4[] = { 0, -1, 0, 1 }, y_4[] = { -1, 0, 1, 0 };
int x, y;
typedef std::vector<std::pair<int, int> > route_type;
typedef std::vector<route_type> route_list;
routes.clear();
//初始只含有一个长为1的路径 （仅含起始点）
routes.push_back(route_type(1, std::make_pair(x0, y0)));
//经过3次遍历扩展，每次扩展根据上一次结果寻找下一步路径
for (size_t i = 0; i < 3; i++)
{
size_t k = routes.size();
// 遍历上一次寻路结果
for (size_t m = 0; m < k; m++)
{
// 4个方向寻找可行的路径
for (int j = 0; j < 4; j++)
{
// 取最后一个点为起始点进行偏移
x = routes[m][i].first + x_4[j];
y = routes[m][i].second + y_4[j];
// 判定移动到的点有效
if (x >= 0 && y >= 0 && x < map_width && y < map_height &&
map[y * map_width + x])
{
// 判定未曾走过
if (std::find(routes[m].begin(), routes[m].end(),
std::make_pair(x, y)) == routes[m].end())
{
// 依据上次寻路结果加上本次可通行点形成一个新的路径
route_type route(routes[m]);
route.push_back(std::make_pair(x, y));
// 添加到寻路结果中
routes.push_back(route);
}
}
}
}
// 删除上次寻路结果
routes.erase(routes.begin(), routes.begin() + k);
}
}
int main(int argc, char * argv[])
{
bool map[25] = {true, true, true, true, false,
true, true, true, false, false,
true, true, false, false, false,
true, false, false, false, false,
false, false, false, false, false
};
printf("------- map --------\n");
for (size_t m = 0; m < 5; ++m)
{
for (size_t n = 0; n < 5; ++n)
{
printf("%d ", map[m * 5 + n]);
}
printf("\n");
}
std::vector<std::vector<std::pair<int, int> > > vec;
mapping(map, 5, 5, 0, 0, vec);
printf("------- routes -------\n");
for (size_t i = 0; i < vec.size(); ++i)
{
int map_tmp[25] = {0};
for (size_t m = 0; m < 25; ++m)
{
map_tmp[m] = map[m] ? 1 : 0;
}
printf("route:%d\n", i);
for (size_t j = 0; j < vec[i].size(); ++j)
{
map_tmp[vec[i][j].second * 5 + vec[i][j].first] = 2;
}
for (size_t m = 0; m < 5; ++m)
{
for (size_t n = 0; n < 5; ++n)
{
printf("%c ",
map_tmp[m * 5 + n] == 0 ? '0' :
map_tmp[m * 5 + n] == 1 ? '1' : '*');
}
printf("\n");
}
}
return 0;
}
