学步园

250...

500...

1000

　　比赛的时候没思路。倒是想到一种trick，想cha人来着，后来发现房间里没有人提交。。。

只想到了预处理出从一个点到另一个点走m步所要用到的情况数，发现dp空间复杂度太高。今天看了一下别人怎么预处理的，我还是太嫩啊。。。

dp[dx][dy][m]表示走m步坐标移动了(dx, dy)所有的情况数。

记忆化搜索一下。

const int MAXN = 55;
const int MOD = 1e9+7;

int dp[MAXN][MAXN][MAXN];

int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

class WolfPackDivTwo {
public:
    int dfs(int dx, int dy, int m) {
        if(dp[dx][dy][m] != -1) return dp[dx][dy][m];
        int res = 0;
        if(m == 0) {
            res = (dx == 0 && dy == 0);
        } else {
            for(int i = 0; i < 4; ++i) {
                int xx = abs(dx + dir[i][0]);
                int yy = abs(dy + dir[i][1]);
                if(xx + yy > m - 1) continue;
                res = (res + dfs(xx, yy, m - 1))%MOD;
            }
        }
        return dp[dx][dy][m] = res;
    }

    int calc(vector <int> x, vector <int> y, int m) {
        int n = x.size(), tx, ty, i, ans = 0;
        CL(dp, -1);
        for(tx = x[0] - m; tx <= x[0] + m; ++tx) {
            for(ty = y[0] - m; ty <= y[0] + m; ++ty) {
                int tmp = 1;
                for(i = 0; i < n; ++i) {
                    int dx = abs(tx - x[i]);
                    int dy = abs(ty - y[i]);
                    if(dx + dy > m) {tmp = 0; continue;}
                    tmp = (tmp*dfs(dx, dy, m))%MOD;
                }
                ans = (ans + tmp)%MOD;
            }
        }
        return ans;
    }
};