#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair <int, int>
#define fi first
#define se second
const int MAXN= 1e3 + 5 ;
int dx[ ] = { 0 ,- 1 ,1 ,0 } ;
int dy[ ] = { 1 ,0 ,0 ,- 1 } ;
char g[ MAXN] [ MAXN] ;
queue < pii> q;
int n, m, a1, b1, c1, d1;
void bfs( int x1, int y1) {
q.push ( { x1, y1} ) ;
while ( ! q.empty ( ) ) {
pii t = q.front ( ) ;
q.pop ( ) ;
for ( int i = 0 ; i < 4 ; i++ ) {
int a = t.first + dx[ i] , b = t.second + dy[ i] ;
if ( a== c1 && b == d1 && g[ a] [ b] == 'X' ) {
cout << "YES" << endl;
exit ( 0 ) ;
}
if ( a >= 1 && a <= n && b >= 1 && b <= m && g[ a] [ b] == '.' ) {
g[ a] [ b] = 'X' ;
q.push ( { a, b} ) ;
}
}
}
cout << "NO" << endl;
exit ( 0 ) ;
}
signed main( ) {
cin >> n >> m;
for ( int i = 1 ; i <= n; i++ ) {
for ( int j = 1 ; j <= m; j++ ) {
cin >> g[ i] [ j] ;
}
}
cin >> a1 >> b1 >> c1 >> d1;
bfs( a1,b1) ;
return 0 ;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgaW50IGxvbmcgbG9uZwojZGVmaW5lIHBpaSBwYWlyIDxpbnQsIGludD4KI2RlZmluZSBmaSBmaXJzdAojZGVmaW5lIHNlIHNlY29uZApjb25zdCBpbnQgTUFYTj0gIDFlMys1OwppbnQgZHhbXSA9IHswLC0xLDEsMH07CmludCBkeVtdID0gezEsMCwwLC0xfTsKCmNoYXIgZ1tNQVhOXVtNQVhOXTsKcXVldWUgPHBpaT4gcTsKaW50IG4sIG0sIGExLCBiMSwgYzEsIGQxOwoKdm9pZCBiZnMoaW50IHgxLCBpbnQgeTEpewogICAgcS5wdXNoKHt4MSwgeTF9KTsKICAgIHdoaWxlKCFxLmVtcHR5KCkpewogICAgICAgIHBpaSB0ID0gcS5mcm9udCgpOwogICAgICAgIHEucG9wKCk7CiAgICAgICAgZm9yIChpbnQgaSA9MDsgaSA8NDsgaSsrKXsKICAgICAgICAgICAgaW50IGEgPSB0LmZpcnN0ICsgZHhbaV0sIGIgPSB0LnNlY29uZCArZHlbaV07CiAgICAgICAgICAgIGlmIChhPT0gYzEgJiYgYiA9PSBkMSAmJiBnW2FdW2JdID09ICdYJyl7CiAgICAgICAgICAgICAgICBjb3V0IDw8ICJZRVMiIDw8IGVuZGw7CiAgICAgICAgICAgICAgICBleGl0KDApOwogICAgICAgICAgICAgICAgCiAgICAgICAgICAgIH0KICAgICAgICAgICAgaWYgKCBhID49IDEgJiYgYSA8PSBuICYmIGIgPj0gMSAmJiBiIDw9IG0gJiYgZ1thXVtiXSA9PSAnLicpewogICAgICAgICAgICAgICAgZ1thXVtiXSA9ICdYJzsKICAgICAgICAgICAgICAgIHEucHVzaCh7YSwgYn0pOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgY291dCA8PCAiTk8iIDw8IGVuZGw7CiAgICBleGl0KDApOwp9CnNpZ25lZCBtYWluKCl7CiAgICBjaW4gPj4gbiA+PiBtOwogICAgZm9yIChpbnQgaSA9MTsgaSA8PSBuOyBpKyspewogICAgICAgIGZvciAoaW50IGogPTE7IGogPD0gbTsgaisrKXsKICAgICAgICAgICAgY2luID4+IGdbaV1bal07CiAgICAgICAgfQogICAgfQogICAgY2luID4+IGExID4+IGIxID4+IGMxID4+IGQxOwogICAgYmZzKGExLGIxKTsKICAgIHJldHVybiAwOwp9
stdin
Tm90ZSB0aGF0IHRoZSBmdW5jdGlvbiBvZiBleGlzdGVuY2Ugb2YgdGhlIGFuc3dlciByZWxhdGl2ZWx5IHRvIHRoZSBtaW5pbXVtIHZhbHVlIG9mIHRoZSBtYXhpbXVtIGluIHRoZSBwYXRoIGlzIG1vbm90b25vdXMuIElmIHdlIHdlcmUgYWJsZSB0byBjb25zdHJ1Y3QgdGhlIHBhdGggd2l0aCBtYXhpbXVtLCBub3QgZ3JlYXRlciB0aGFuIHgKLCB3ZSBhcmUgYWJsZSB0byBjb25zdHJ1Y3QgdGhlIHBhdGggd2l0aCBtYXhpbXVtLCBub3QgZ3JlYXRlciB0aGFuIHgrMQouIFRoaXMgbGVhZHMgdG8gdGhlIGlkZWEgb2YgYmluYXJ5IHNlYXJjaCB0aGUgYW5zd2VyLgoKTGV0IGJpbmFyeSBzZWFyY2ggdG8gZml4IHNvbWUgaW50ZWdlciB4Ci4gV2UgaGF2ZSB0byBjaGVjaywgaWYgdGhlcmUgaXMgYSBwYXRoIGluIHRoZSBncmFwaCwgdGhhdCBjb25zaXN0cyBvZiBrJm1pbnVzOzEKIGVkZ2VzIGFuZCB0aGUgbWF4aW11bSBvbiB0aGlzIHBhdGggaXMgbm90IGdyZWF0ZXIgdGhhbiB4Ci4gSW4gdGhlIGJlZ2lubmluZyBsZXQncyBsZWF2ZSBpbiBjb25zaWRlcmF0aW9uIG9ubHkgdmVydGljZXMgd2hpY2ggdmFsdWVzIGFyZSBub3QgZ3JlYXRlciB0aGFuIHgKLiBOb3cgd2UgbmVlZCB0byBjaGVjayBpZiB0aGUgbmVlZGVkIHBhdGggZXhpc3QgaW4gdGhlIHJlc3VsdGluZyBncmFwaC4KCklmIHRoZXJlIGlzIGEgY3ljbGUgaW4gdGhlIGdyYXBoLCB0aGVyZSBpcyBhIHBhdGggb2YgZXZlcnkgbGVuZ3RoIGluIGl0LCBzbyB0aGVyZSBpcyBhIHBhdGggb2YgbGVuZ3RoIGsmbWludXM7MQouIE90aGVyd2lzZSB3ZSBoYXZlIGEgZGlyZWN0ZWQgYWN5Y2xpYyBncmFwaC4gTGV0J3MgZmluZCBhIGxvbmdlc3QgcGF0aCBpbiBpdCBhbmQgY29tcGFyZSBpdHMgbGVuZ3RoIHdpdGggayZtaW51czsxCi4gTGV0J3Mgc29ydCB0aGUgZ3JhcGggdG9wb2xvZ2ljYWxseSBhbmQgY2FsY3VsYXRlIGRwW3ZdCiAmbWRhc2g7IHRoZSBsZW5ndGggb2YgdGhlIGxvbmdlc3QgcGF0aCBpbiB0aGUgZ3JhcGggdGhhdCBiZWdpbnMgaW4gdmVydGV4IHYKLCBpdCdzIGEgd2VsbC1rbm93biBjbGFzc2ljYWwgcHJvYmxl
Note that the function of existence of the answer relatively to the minimum value of the maximum in the path is monotonous. If we were able to construct the path with maximum, not greater than x
, we are able to construct the path with maximum, not greater than x+1
. This leads to the idea of binary search the answer.
Let binary search to fix some integer x
. We have to check, if there is a path in the graph, that consists of k−1
edges and the maximum on this path is not greater than x
. In the beginning let's leave in consideration only vertices which values are not greater than x
. Now we need to check if the needed path exist in the resulting graph.
If there is a cycle in the graph, there is a path of every length in it, so there is a path of length k−1
. Otherwise we have a directed acyclic graph. Let's find a longest path in it and compare its length with k−1
. Let's sort the graph topologically and calculate dp[v]
— the length of the longest path in the graph that begins in vertex v
, it's a well-known classical proble