Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
2.3 kB
1
Indexable
Never
//Dai Ca Di Hoc
#include <bits/stdc++.h>
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define reset(x) memset(x, 0,sizeof(x))
#define Rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define For(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define MIN(x,y) if (x > (y)) x = (y)
#define MAX(x,y) if (x < (y)) x = (y)
#define PB push_back
#define mp make_pair
#define F first
#define S second
#define maxn 505
#define MOD 1000000009
#define remain(x) if (x > MOD) x -= MOD
#define pii pair<int, int>
#define vi vector<int>
#define vii vector< pii >
#define bit(x, i) (((x) >> (i)) & 1)
#define Task "park"

using namespace std;

typedef long long ll;
typedef long double ld;
char a[maxn][maxn];

const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

struct data{
    int u, v, delta;
};

data q[maxn*maxn*2];
int d[maxn][maxn], f[maxn][maxn][2], m, n;

inline void Add(int &x, int y){
    x += y;
    if (x >= MOD) x -= MOD;
}

void BFS(){
    int bot = 1, top = 1;
    while (bot <= top){
        int u = q[bot].u;
        int v = q[bot].v;
        int delta = q[bot++].delta;
		int dist = d[u][v] + delta*2 + 1; // khoang cach moi
        For(i, 0, 3){
            int x = u + dx[i];
            int y = v + dy[i];
            if (a[x][y] == '#') continue;
            if (d[x][y] == -1) d[x][y] = d[u][v] + 1, q[++top] = {x, y, 0};
            if (d[x][y] == dist){
                Add(f[x][y][0], f[u][v][delta]);
            } else
                if (d[x][y] + 2 == dist){
                    if (f[x][y][1] == 0) q[++top] = {x,y,1};
                    Add(f[x][y][1], f[u][v][delta]);
                }
        }
    }
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen(Task".inp", "r", stdin);
    //freopen(Task".out", "w", stdout);
    cin >> m >> n;
    memset(a, '#', sizeof(a));
    memset(d, -1, sizeof d);
    int pe, qe;
    For(i, 1, m)
        For(j, 1, n) {
            cin >> a[i][j];
            if (a[i][j] == 'E') {
                q[1] = data{i,j,0};
                d[i][j] = 0;
                f[i][j][0] = 1;
            }
            if (a[i][j] == 'X') pe = i, qe = j;
        }
    BFS();
    cout << f[pe][qe][1];
    return 0;
}

Leave a Comment