一马当先,C++ 之解法
2018-09-07 本文已影响0人
狐度计算
一马当先是一道经典的动态规划问题, 今天狐狐尝试用C++来解此题：
下过象棋的人都知道，马只能走'日'字形（包括旋转90°的日），现在想象一下，给你一个n行m列网格棋盘，棋盘的左下角有一匹马，请你计算至少需要几步可以将它移动到棋盘的右上角，若无法走到，则输出-1. 如n=1，m=2,则至少需要1步；若n=1，m=3,则输出-1。
解法一（Solution1）：
使用vector创建动态二维数组
#include <vector>
#include <iostream>
using namespace std;
void step_board(int n, int m) {vector> board(n+1, vector(m+1));
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < m + 1; j++)
{
board[i][j] = -1;
}
}
board[0][0] = 0;
int r[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int c[] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int flag = 1;
while (flag == 1) {
flag = 0;
for (int row = 0; row < n + 1; row++) {
for (int col = 0; col < m + 1; col++) {
if (board[row][col] == -1) {
int minstep = 1000000;
for (int i = 0; i < 8; i++) {
if (row + r[i] >= 0 && row + r[i] < n + 1 && col + c[i] >= 0
&& col + c[i] < m + 1 && board[row + r[i]][col + c[i]] >= 0
&& board[row + r[i]][col + c[i]] < minstep) {
minstep = board[row + r[i]][col + c[i]] + 1;
}
}
if (minstep < 1000000) {
board[row][col] = minstep;
flag = 1;
}
}
}
}
}
cout << "The least step:" << to_string(board[n][m]) << endl;
}
解法二（Solution2）:
使用指针pointer创建动态二维数组
#include <iostream>
using namespace std;
void step_board(int n, int m) {
int **board = new int*[n];
for (int i = 0; i < n + 1; i++){
board[i] = new int[m];
}
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < m + 1; j++)
{
board[i][j] = -1;
}
}
board[0][0] = 0;
int r[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int c[] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int flag = 1;
while (flag == 1) {
flag = 0;
for (int row = 0; row < n + 1; row++) {
for (int col = 0; col < m + 1; col++) {
if (board[row][col] == -1) {
int minstep = 1000000;
for (int i = 0; i < 8; i++) {
if (row + r[i] >= 0 && row + r[i] < n + 1 && col + c[i] >= 0
&& col + c[i] < m + 1 && board[row + r[i]][col + c[i]] >= 0
&& board[row + r[i]][col + c[i]] < minstep) {
minstep = board[row + r[i]][col + c[i]] + 1;
}
}
if (minstep < 1000000) {
board[row][col] = minstep;
flag = 1;
}
}
}
}
}
cout << "The least step:" << to_string(board[n][m]) << endl;
}
