一馬當(dāng)先是一道經(jīng)典的動(dòng)態(tài)規(guī)劃問題, 今天狐狐嘗試用C++來解此題：
下過象棋的人都知道，馬只能走'日'字形（包括旋轉(zhuǎn)90°的日），現(xiàn)在想象一下，給你一個(gè)n行m列網(wǎng)格棋盤，棋盤的左下角有一匹馬，請(qǐng)你計(jì)算至少需要幾步可以將它移動(dòng)到棋盤的右上角，若無法走到，則輸出-1. 如n=1，m=2,則至少需要1步；若n=1，m=3,則輸出-1。
解法一（Solution1）：
使用vector創(chuàng)建動(dòng)態(tài)二維數(shù)組
#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創(chuàng)建動(dòng)態(tài)二維數(shù)組
#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;
}
