試題:跳馬問題

#include <iomanip>
#include <iostream>
using namespace std;

const int row = 5;
const int col = 5;

bool move(int r, int c, int & index, int step[row][col])
{
    if (r >= 0 && c >= 0 && r < row && c < col && 0 == step[r][c]) {
        step[r][c] = ++index;
        if (row * col == index
        || move(r - 1, c - 2, index, step)
        || move(r - 1, c + 2, index, step)
        || move(r - 2, c - 1, index, step)
        || move(r - 2, c + 1, index, step)
        || move(r + 1, c - 2, index, step)
        || move(r + 1, c + 2, index, step)
        || move(r + 2, c - 1, index, step)
        || move(r + 2, c + 1, index, step))
        {
            return true;
        }
        else
        {
            step[r][c] = 0;
            --index;
        }
    }
    return false;
}

void trymove(int r, int c, int & count, int & index, int step[row][col])
{
    if (r >= 0 && c >= 0 && r < row && c < col && 0 == step[r][c]) {
        step[r][c] = ++index;
        if (row * col == index)
        {
            ++count;
        }
        else
        {
            trymove(r - 1, c - 2, count, index, step);
            trymove(r - 1, c + 2, count, index, step);
            trymove(r - 2, c - 1, count, index, step);
            trymove(r - 2, c + 1, count, index, step);
            trymove(r + 1, c - 2, count, index, step);
            trymove(r + 1, c + 2, count, index, step);
            trymove(r + 2, c - 1, count, index, step);
            trymove(r + 2, c + 1, count, index, step);
        }
        step[r][c] = 0;
        --index;
    }
}

void show(int step[row][col])
{
    for (int r = 0; r < row; ++r)
    {
        for (int c = 0; c < col; ++c)
        {
            cout << setfill('0') << setw(2) << step[r][c];
            if (col - 1 != c)
            {
                cout << "--";
            }
        }
        cout << endl;
        if (row - 1 != r)
        {
            for (int i = 0; i < col; ++i)
            {
                cout << "|   ";
            }
            cout << endl;
        }
    }
}

void firstmove()
{
    int index = 0;
    int step[row][col] = {0};
    if (move(0, 0, index, step))
    {
        show(step);
    }
    else
    {
        cout << "no solution" << endl;
    }
}

void getmoveways()
{
    int count = 0;
    int index = 0;
    int step[row][col] = {0};
    trymove(0, 0, count, index, step);
    cout << endl << "---------- " << count << " ----------" << endl;
}

int main()
{
    firstmove();
    getmoveways();
    return 0;
}
           

firstmove()在8X8時還可以, 再上去就出不來了, getmoveways()在5X6時就要半分鐘了, 慢

找了下别人寫的, 都是把8種跳的方式用數組儲存起來做的