题目的解法（思路正确但是时间复杂度过高的错误解法）

前言：仅为了纪念那个不甘的心(悲)

1.P1002 [NOIP2002 普及组] 过河卒（洛谷）

#include<stdio.h>
#include<iostream>
using namespace std;

int ans;//答案
int x_end, y_end;//终点
int x_horse, y_horse;//马的坐标

int box[1000][1000];//地图
int mar[1000][1000];//走过的标记

int dir_soldier[10][10] = { {0,0},{0,1},{1,0}};
int dir_horse[10][10] = { {0,0},{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1}, {2,-1},{-2,-1} };

void dfs(int x, int y)
{
    if (x == x_end || y == y_end)
    {
        ans++;
        return;
    }//当走到答案时，ans++并返回上一步

    for (int i = 1; i <= 2; i++)
    {
        int tx = x + dir_soldier[i][1];
        int ty = y + dir_soldier[i][0];
        if (tx<0 || ty<0 || tx>x_end || ty>y_end || box[tx][ty] == 1 || mar[tx][ty] == 1)
        {
            continue;
        }
        mar[x][y] = 1;
        dfs(tx, ty);
        mar[x][y] = 0;
    }
    return;
}

int main()
{
    cin >> x_end >> y_end >> x_horse >> y_horse;

    box[x_horse][y_horse] = 1;
    for (int i = 1; i <= 8; i++)
    {
        int tx = x_horse + dir_horse[i][0];
        int ty = y_horse + dir_horse[i][1];
        if (tx<0 || ty<0 || tx>x_end || ty>y_end )
        {
            continue;
        }//不能标记超出数组范围的地方
        box[tx][ty] = 1;
    }//将马能经过的地方标记

    mar[0][0] = 1;
    dfs(0, 0);
    cout << ans << endl;//输出答案
    return 0;
}