学步园

解题思路：

这题一看到，卧槽，好简单，无脑dfs就可以走完，于是不到5分钟码出来了个dfs，没想到光荣的T了，，，然后翻了翻题解，才知道要用棋盘dp，以前一直不会，现在就来学学吧。

T的代码：

# include<cstdio>
# include<iostream>

using namespace std;

# define MAX 20

int grid[MAX][MAX];
int vis[MAX][MAX];

int edx,edy;
int mx,my;
int res;

int next[2][2] = { {0,1},{1,0} };
int next2[9][2] = { {0,0},{-1,-2},{-1,2},{-2,-1},{-2,1},{1,-2},{1,2},{2,-1},{2,1} };


int judge ( int x,int y )
{
    if ( x < 0||x > edx||y < 0||y > edy||vis[x][y] )
    {
        return 0;
    }

    for ( int i = 0;i < 9;i++ )
    {
        if ( x==mx+next2[i][0] && y==my+next2[i][1] )
        {
            return 0;
        }
    }
    return 1;
}


void dfs( int x,int y )
{
    if ( x == edx && y == edy )
    {
        res++;
        return;
    }

    for ( int i = 0;i < 2;i++ )
    {
        int n_x = x+next[i][0];
        int n_y = y+next[i][1];

        if ( judge(n_x,n_y) )
        {
            vis[n_x][n_y] = 1;
            dfs( n_x,n_y );
            vis[n_x][n_y] = 0;
        }
    }

}

int main(void)
{
    while ( cin>>edx>>edy>>mx>>my )
    {
        vis[0][0] = 1;
        dfs( 0,0 );
        cout<<res<<endl;
    }



    return 0;
}

棋盘dp思想：

这道题是一个由于存在无后效性的方法，所以呢，我们应该想到dp的分层处理，就是说，先从左到右走一遍，然后再从上到下走一遍，把其中存在能够走的点晒出来，

不能走的直接break，因为卒只有两种走法，要么从左->右走，要么从上->下的走。然后还需要明确一个就是dp[0][0] = 1.

哦，说了，这么多，都忘记定义这个题的状态和状态转移方程是什么了，我们知道状态就是dp[i][j]表示的是从从（0,0）->(i,j)的方法总数，那我们最后输出dp[edx][edy]就是最终的结果了~

接下来来说说状态转移方程是什么？在最后一个点上，(edx,edy)仅仅可以由两个点走过来，一个点是(edx-1,edy)，另一点是(edx,edy-1)，然后呢，方法数就可以依次类推了,这样就得到了状态转移方程：dp[i][j] = dp[i-1][j]+dp[i][j-1];

好了，不多说了，上代码：

# include<cstdio>
# include<iostream>

using namespace std;

# define MAX 20

int edx,edy;
int mx,my;
int dp[MAX][MAX];

int next2[9][2] = { {0,0},{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2} };

int judge ( int x,int y )
{

    for ( int i = 0;i < 9;i++ )
    {
        if ( x==mx+next2[i][0] && y==my+next2[i][1] )
        {
            return 0;
        }
    }
    return 1;
}


int main(void)
{
    while ( cin>>edx>>edy>>mx>>my )
    {

    dp[0][0] = 1;
    for ( int i = 1;i <= edx;i++ )
    {
        if ( judge(i,0) )
        {
            dp[i][0] = 1;
        }
        else
        {
            break;
        }
    }
    for ( int j = 1;j <= edy;j++ )
    {
        if ( judge(0,j) )
        {
            dp[0][j] = 1;
        }
        else
        {
            break;
        }
    }

    for ( int i = 1;i <= edx;i++ )
    {
        for ( int j = 1;j <= edy;j++ )
        {
            if ( judge(i,j) )
            {
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }

    }
        cout<<dp[edx][edy]<<endl;
    }

    return 0;
}