HDU1078 Fat Mouse and Chess

一个记忆化搜索的题目，参考了网上的代码才写出来的。
dfs（x，y）表示从x，y开始走的话最大的结果是多少。每一次搜索上下左右k步中 最大的那一个 还有一点dp的思想。dp数组用来记录结果，并且防止重复判断。

#include<iostream>
#include<cstring>

using namespace std;

const int maxn = 110;
int G[maxn][maxn];
int dp[maxn][maxn];
int dir[4][2]={0,1,0,-1,1,0,-1,0};//一个表示方向的数组
int n,k;
int dfs(int a,int b)
{
    int ans = 0;
    if(!dp[a][b])
    {
        for(int i = 1 ; i <= k ; i++)
        {
            for(int j = 0 ; j < 4 ; j++)
            {
                int x=a+dir[j][0]*i,y=b+dir[j][1]*i;//xy是要遍历的坐标
                if(x>=0&&x<n&&y>=0&&y<n)
                {
                    if(G[x][y]>G[a][b])
                    {

                        ans = max(ans,dfs(x,y));
                    }
                }
            }
        }
        dp[a][b]=ans+G[a][b];
    }
    return dp[a][b];

}
int main()
{
    while(cin>>n>>k&&!(n==-1&&k==-1))
    {
        memset(G,0,sizeof(G));
        memset(dp,0,sizeof(dp));
        for(int i = 0 ; i < n ; i++)
        {
            for(int j = 0; j < n ; j++)
            {
                cin >> G[i][j];
            }
        }
        dfs(0,0);
        cout<<dp[0][0]<<endl;
    }
    return 0;
}