Untitled
//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