NC16735（网格图 ）

感受

思路

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
struct node{
    int dfn;
    int val;
}f[2][205][205][5];
int dx[] = {-1, 1, 0, 0, 0};
int dy[] = {0, 0, -1, 1, 0};
int n, m, t, x1, yy, d, x2, y2;
int my_abs(int x){
    return x < 0 ? -x : x;
}
bool check(int x, int y){
    return my_abs(x - x1) <= d && my_abs(y - yy) <= d;
}
void solve(int oo, int x, int y, int k, int dfn, int o, int lx, int ly, int lk){
    if(f[oo][x][y][k].dfn == dfn){
        f[oo][x][y][k].val += f[o][lx][ly][lk].val;
        f[oo][x][y][k].val %= mod;
    }
    else{
        f[oo][x][y][k].dfn = dfn;
        f[oo][x][y][k].val = f[o][lx][ly][lk].val;
    }
}
int main(){
    scanf("%d%d%d%d%d%d%d%d", &n, &m, &t, &x1, &yy, &d, &x2, &y2);
    f[0][1][1][4] = (node){0, 1};
    int o = 0;
    for(int i = 0; i < t; i++, o ^= 1){
        for(int x = 1; x <= n; x++){
            for(int y = 1; y <= m; y++){
                for(int k = 0; k <= 4; k++){
                    int nx, ny, oo = o ^ 1;
                    if(k != 4 && check(x, y)){
                        if(f[o][x][y][k].dfn == i){
                            solve(oo, x, y, 4, i + 1, o, x, y, k);
                            nx = x + dx[k]; ny = y + dy[k];
                            solve(oo, nx, ny, k, i + 1, o, x, y, k);
                        }
                    }
                    else{
                        if(f[o][x][y][k].dfn == i){
                            for(int dir = 0; dir <= 4; dir++){
                                nx = x + dx[dir]; ny = y + dy[dir];
                                solve(oo, nx, ny, dir, i + 1, o, x, y, k);
                            }
                        }

                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0; i <= 4; i++){
        if(f[o][x2][y2][i].dfn == t){
            ans += f[o][x2][y2][i].val; ans %= mod;
        }
    }
    printf("%d\n", ans);
    return 0;
}