马拦过河卒 （C++代码）

            深搜竟然过了=.=!

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
typedef long long ll;
//int DP[21][21] = { 1 };
bool vis[21][21];
int nx, ny, fx, fy;
int tot;
int dx[2] = { 0,1 };
int dy[2] = { 1,0 };
void Vis(int x, int y){
    vis[x][y] = true;
    vis[x - 1][y - 2] = true;
    vis[x - 2][y - 1] = true;
    vis[x - 2][y + 1] = true;
    vis[x - 1][y + 2] = true;
    vis[x + 1][y - 2] = true;
    vis[x + 2][y - 1] = true;
    vis[x + 2][y + 1] = true;
    vis[x + 1][y + 2] = true;
}
void dfs(int x, int y){    
if (x == nx && y == ny)
    {
        tot++;        
        return;
    }    
        for (int i = 0; i < 2; i++)
        {        
             int fx = x + dx[i];        
             int fy = y + dy[i];        
             if (!vis[fx][fy] && fx <= nx && fy <= ny)
            {
                vis[fx][fy] = true;
                dfs(fx, fy);
                vis[fx][fy] = false;
            }
        }
}
int main()
{    
    cin >> nx >> ny >> fx >> fy;
    Vis(fx, fy);
    dfs(0, 0);    
    cout << tot << endl;    
    return 0;
}

            另外附上DP的代码

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
typedef long long ll;
ll DP[23][23] = { 1 };
bool vis[23][23];
int nx, ny, fx, fy;
void Vis(int x, int y)
{
	vis[0][0] = true;
	vis[x][y] = true;
	if (x - 1 >= 0 && y - 2 >= 0)
		vis[x - 1][y - 2] = true;
	if (x - 2 >= 0 && y - 1 >= 0)
		vis[x - 2][y - 1] = true;
	if (x - 2 >= 0 && y + 1 <= ny)
		vis[x - 2][y + 1] = true;
	if (x - 1 >= 0 && y + 2 <= ny)
		vis[x - 1][y + 2] = true;
	if (x + 1 <= nx && y - 2 >= 0)
		vis[x + 1][y - 2] = true;
	if (x + 2 <= nx && y - 1 >= 0)
		vis[x + 2][y - 1] = true;
	if (x + 2 <= nx && y + 1 <= ny)
		vis[x + 2][y + 1] = true;
	if (x + 1 <= nx && y + 2 <= ny)
		vis[x + 1][y + 2] = true;
}
int main()
{
	cin >> nx >> ny >> fx >> fy;
	Vis(fx, fy);
	for(int i=0;i<=nx;i++)
		for (int j = 0; j <= ny; j++)
		{
			if (!vis[i][j])
			{
				DP[i][j] = DP[i == 0 ? i : i - 1][j] + DP[i][j == 0 ? j : j - 1];
			}
		}
	cout << DP[nx][ny] << endl;
	return 0;
}