# Untitled

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)

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){
} else
if (d[x][y] + 2 == dist){
if (f[x][y][1] == 0) q[++top] = {x,y,1};
}
}
}
}

int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
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;
}

```