棋盘跳马
从指定位置跳到指定位置的最短路径
马走日，存在蹩腿
/**
* 棋盘跳马
* 按照中国象棋跳马规则
*/
#include <stdio.h>
#include <vector>
#include <utility>
#include <time.h>
#define print_board(board, ...) {\
printf(__VA_ARGS__); \
printf("\n"); \
print_board_(board);\
}
#define ROW 10
#define COLUMN 9
using namespace std;
void print_board_(int board[][COLUMN]);
void print_path(vector<int> path, vector<pair<int, int>> history_pos);
void print_path_in_board(vector<int> path, vector<pair<int, int>> history_pos,
int board[][COLUMN]);
void run();
vector<pair<int, int>> get_legal_move(int board[][COLUMN], pair<int, int> pos);
vector<pair<int, int>> get_legal_move_horse(int board[][COLUMN], pair<int, int> pos);
bool check_horse_move(int board[][COLUMN], pair<int, int> init_pos, pair<int, int> pos);
// 检查试跳是否超出边界，是否被占用
bool check_border_occupy(int board[][COLUMN], pair<int, int> pos);
// 检查是否曾经到达过；如果曾经到达过，则说明当前路径不是最短
bool check_history(vector<pair<int, int>> history_pos, pair<int, int> pos);
bool check_equal(pair<int, int> p1, pair<int, int> p2);
int main(int argc, char** argv) {
clock_t start, end;
start = clock();
run();
end = clock();
printf("time cost: %.3f ms\n", (end-start)*1000./CLOCKS_PER_SEC);
return 0;
}
void run() {
int board[ROW][COLUMN] = {
{5,4,3,2,1,2,3,4,5},
{0,0,0,0,0,0,0,0,0},
{0,6,0,0,0,0,0,6,0},
{7,0,7,0,7,0,7,0,7},
{0,0,0,0,0,0,0,0,0},
//{0,0,0,0,0,0,0,0,0},
{0,0,13,0,0,0,0,0,0},
{17,0,17,0,17,0,17,0,17},
{0,16,0,0,0,0,0,16,0},
{0,0,0,0,0,0,0,0,0},
//{15,14,13,12,11,12,13,14,15},
{15,14,0,12,11,12,13,14,15},
};
print_board(board, "origin:");
// 9,1 -> 6,3
pair<int, int> init_pos{9, 1};
pair<int, int> aim_pos{6, 3};
// test get_legal_move
vector<pair<int, int>> poslist = get_legal_move(board, init_pos);
for (pair<int, int> pos : poslist) {
board[pos.first][pos.second] = 9;
print_board(board, "测试 get_legal_move ret:");
board[pos.first][pos.second] = 0;
}
// 利用栈进行广度优先搜索
// 路径存放在 path_list 中，历史位置存放在 history_pos 中
// step 代表步数，即广度搜索的层数;count 代表当前层还有几个位置没有处理
printf("--------------\n");
vector<pair<int, int>> history_pos{init_pos, aim_pos};
vector<pair<int, int>> stack_pos{init_pos};
vector<vector<int>> path_list{{0}};
int step = 1;
int count = 1;
bool arrive = false;
while (!stack_pos.empty()) {
vector<pair<int, int>> poslist = get_legal_move(board, *(stack_pos.begin()));
for (auto pos = poslist.begin(); pos != poslist.end(); ++pos) {
if (check_equal(*pos, aim_pos)) {
auto path = path_list[0];
path.push_back(1);
path_list.push_back(path);
arrive = true;
//print_path(*(path_list.end()-1), history_pos);
//board[pos->first][pos->second] = 9;
//print_board(board, "arrived step %d:(%d, %d)", step, pos->first, pos->second);
//board[pos->first][pos->second] = 0;
// 搜索所有最短路径，如果只搜索到一条就停止，则打开此处和下面的break
// 同时需要删除 path_list 中其他的路径
//break;
}
if (!check_history(history_pos, *pos) && !arrive) {
history_pos.push_back(*pos);
stack_pos.push_back(*pos);
auto path = path_list[0];
path.push_back(history_pos.size()-1);
path_list.push_back(path);
//print_path(*(path_list.end()-1), history_pos);
//board[pos->first][pos->second] = 9;
//print_board(board, "step %d:(%d, %d)", step, pos->first, pos->second);
//board[pos->first][pos->second] = 0;
}
}
if (step > 100) {
printf("step too large, canot find a path to (%d, %d).\n",
aim_pos.first, aim_pos.second);
break;
}
//if (arrive) {
// printf("arrived, step: %d.\n", step);
// //break;
//}
stack_pos.erase(stack_pos.begin());
path_list.erase(path_list.begin());
if (--count == 0) {
count = stack_pos.size();
++step;
}
}
// 打印路径
for (auto path : path_list) {
print_path_in_board(path, history_pos, board);
}
}
bool check_history(vector<pair<int, int>> history_pos, pair<int, int> pos) {
for (auto p : history_pos) {
if (check_equal(p, pos)) {
return true;
}
}
return false;
}
bool check_equal(pair<int, int> p1, pair<int, int> p2) {
return p1.first == p2.first && p1.second == p2.second;
}
vector<pair<int, int>> get_legal_move(int board[][COLUMN], pair<int, int> pos) {
// 以马为例
return get_legal_move_horse(board, pos);
}
vector<pair<int, int>> get_legal_move_horse(int board[][COLUMN], pair<int, int> pos) {
vector<pair<int, int>> ret;
pair<int, int> pos1;
if (pos.first > 1 && board[pos.first-1][pos.second] == 0) {
pos1.first = pos.first-2;
pos1.second = pos.second-1;
if (check_border_occupy(board, pos1)) {
ret.push_back(pos1);
}
pos1.first = pos.first-2;
pos1.second = pos.second+1;
if (check_border_occupy(board, pos1)) {
ret.push_back(pos1);
}
}
if (pos.first < ROW-2 && board[pos.first+1][pos.second] == 0) {
pos1.first = pos.first+2;
pos1.second = pos.second-1;
if (check_border_occupy(board, pos1)) {
ret.push_back(pos1);
}
pos1.first = pos.first+2;
pos1.second = pos.second+1;
if (check_border_occupy(board, pos1)) {
ret.push_back(pos1);
}
}
if (pos.second > 1 && board[pos.first][pos.second-1] == 0) {
pos1.first = pos.first-1;
pos1.second = pos.second-2;
if (check_border_occupy(board, pos1)) {
ret.push_back(pos1);
}
pos1.first = pos.first+1;
pos1.second = pos.second-2;
if (check_border_occupy(board, pos1)) {
ret.push_back(pos1);
}
}
if (pos.second < ROW-2 && board[pos.first][pos.second+1] == 0) {
pos1.first = pos.first-1;
pos1.second = pos.second+2;
if (check_border_occupy(board, pos1)) {
ret.push_back(pos1);
}
pos1.first = pos.first+1;
pos1.second = pos.second+2;
if (check_border_occupy(board, pos1)) {
ret.push_back(pos1);
}
}
return ret;
}
bool check_border_occupy(int board[][COLUMN], pair<int, int> pos) {
int row = pos.first;
int col = pos.second;
return row >= 0 && row < ROW && col >= 0 && col < COLUMN
&& board[row][col] == 0;
}
void print_board_(int board[][COLUMN]) {
for (int i = 0; i < ROW; ++i) {
for (int j = 0; j < COLUMN; ++j) {
printf("\033[");
switch (board[i][j]) {
case 1:
printf("1;31;40m帅 ");
break;
case 11:
printf("1;32;40m将 ");
break;
case 2:
printf("1;31;40m士 ");
break;
case 12:
printf("1;32;40m士 ");
break;
case 3:
printf("1;31;40m相 ");
break;
case 13:
printf("1;32;40m象 ");
break;
case 4:
printf("1;31;40m马 ");
break;
case 14:
printf("1;32;40m馬 ");
break;
case 5:
printf("1;31;40m车 ");
break;
case 15:
printf("1;32;40m車 ");
break;
case 6:
printf("1;31;40m炮 ");
break;
case 16:
printf("1;32;40m炰 ");
break;
case 7:
printf("1;31;40m兵 ");
break;
case 17:
printf("1;32;40m卒 ");
break;
case 0:
printf("1;0;40m · ");
break;
default:
printf("1;0;40m%02d ", board[i][j]);
break;
}
printf("\033[0m");
}
printf("\n");
}
printf("\n");
}
void print_path(vector<int> path, vector<pair<int, int>> history_pos) {
pair<int, int> pos;
for (int idx = 0; idx < path.size(); ++idx) {
pos = history_pos[path[idx]];
printf("%d(%d, %d)", idx, pos.first, pos.second);
if (idx != path.size()-1) {
printf(" -> ");
}
}
printf("\n");
}
void print_path_in_board(vector<int> path, vector<pair<int, int>> history_pos,
int board[][COLUMN]) {
pair<int, int> pos;
int idx;
printf("print path: ");
for (idx = 0; idx < path.size(); ++idx) {
pos = history_pos[path[idx]];
board[pos.first][pos.second] = idx + 50;
printf("%d(%d, %d)", idx, pos.first, pos.second);
if (idx != path.size()-1) {
printf(" -> ");
}
}
printf("\n");
print_board_(board);
for (idx = 0; idx < path.size(); ++idx) {
pos = history_pos[path[idx]];
board[pos.first][pos.second] = 0;
}
}
运行结果：（颜色显式不出来）
$ g++ -o horse horse.cpp && ./horse
origin:
车 马 相 士 帅 士 相 马 车
· · · · · · · · ·
· 炮 · · · · · 炮 ·
兵 · 兵 · 兵 · 兵 · 兵
· · · · · · · · ·
· · 象 · · · · · ·
卒 · 卒 · 卒 · 卒 · 卒
· 炰 · · · · · 炰 ·
· · · · · · · · ·
車 馬 · 士 将 士 象 馬 車
测试 get_legal_move ret:
车 马 相 士 帅 士 相 马 车
· · · · · · · · ·
· 炮 · · · · · 炮 ·
兵 · 兵 · 兵 · 兵 · 兵
· · · · · · · · ·
· · 象 · · · · · ·
卒 · 卒 · 卒 · 卒 · 卒
09 炰 · · · · · 炰 ·
· · · · · · · · ·
車 馬 · 士 将 士 象 馬 車
测试 get_legal_move ret:
车 马 相 士 帅 士 相 马 车
· · · · · · · · ·
· 炮 · · · · · 炮 ·
兵 · 兵 · 兵 · 兵 · 兵
· · · · · · · · ·
· · 象 · · · · · ·
卒 · 卒 · 卒 · 卒 · 卒
· 炰 09 · · · · 炰 ·
· · · · · · · · ·
車 馬 · 士 将 士 象 馬 車
测试 get_legal_move ret:
车 马 相 士 帅 士 相 马 车
· · · · · · · · ·
· 炮 · · · · · 炮 ·
兵 · 兵 · 兵 · 兵 · 兵
· · · · · · · · ·
· · 象 · · · · · ·
卒 · 卒 · 卒 · 卒 · 卒
· 炰 · · · · · 炰 ·
· · · 09 · · · · ·
車 馬 · 士 将 士 象 馬 車
--------------
print path: 0(9, 1) -> 1(7, 2) -> 2(8, 4) -> 3(6, 3)
车 马 相 士 帅 士 相 马 车
· · · · · · · · ·
· 炮 · · · · · 炮 ·
兵 · 兵 · 兵 · 兵 · 兵
· · · · · · · · ·
· · 象 · · · · · ·
卒 · 卒 53 卒 · 卒 · 卒
· 炰 51 · · · · 炰 ·
· · · · 52 · · · ·
車 50 · 士 将 士 象 馬 車
print path: 0(9, 1) -> 1(8, 3) -> 2(7, 5) -> 3(6, 3)
车 马 相 士 帅 士 相 马 车
· · · · · · · · ·
· 炮 · · · · · 炮 ·
兵 · 兵 · 兵 · 兵 · 兵
· · · · · · · · ·
· · 象 · · · · · ·
卒 · 卒 53 卒 · 卒 · 卒
· 炰 · · · 52 · 炰 ·
· · · 51 · · · · ·
車 50 · 士 将 士 象 馬 車
time cost: 0.355 ms
颜色示例：
