Submission #188382

---

Source Code Expand

#include <vector>
#include <iostream>
#include <set>
#include <cstdio>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <tuple>
#include <algorithm>
#include <limits>
#include <map>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
double dp[2][1010][1010] = {};
int dir[4][2] = {
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1},
};
int main() {
    int n, d;
    int x, y;
    cin >> n >> d;
    cin >> x >> y;
    if (x%d || y%d) {
        printf("0\n");
        return 0;
    }
    x /= d; y /= d;
    x = abs(x); y = abs(y);
    if (x+y > n) {
        printf("0\n");
        return 0;
    }
    dp[0][0][0] = 1;
    for (int t = 1; t <= n; t++) {
        fill_n(dp[t%2][0], 1010*1010, 0);
        for (int i = 0; i <= t; i++) {
            for (int j = 0; j <= t-i; j++) {
                for (int k = 0; k < 4; k++) {
                    int ii = i+dir[k][0], jj = j+dir[k][1];
                    ii = abs(ii); jj = abs(jj);
                    if (n < ii || n < jj) continue;
                    dp[t%2][i][j] += dp[1-t%2][ii][jj]/4;
                }
            }
        }
    }
    printf("%.20f\n", dp[n%2][x][y]);
}

Submission Info

Judge Result