1 | #include<bits/stdc++.h> |
2 | using namespace std; |
3 | const int N=510; |
4 | int n,m; |
5 | char mp[N][N]; |
6 | struct node |
7 | { |
8 | int x,y,step; |
9 | }; |
10 | queue<node>q; |
11 | node s,t; |
12 | int dx[4]={1,-1,0,0}; |
13 | int dy[4]={0,0,1,-1}; |
14 | int vis[N][N]; |
15 | bool flag=1; |
16 | int ans=0; |
17 | void bfs() |
18 | { |
19 | while(!q.empty()) |
20 | { |
21 | node tmp=q.front(); |
22 | q.pop(); |
23 | // cout<<tmp.x<<' '<<tmp.y<<endl; |
24 | if(tmp.x==t.x&&tmp.y==t.y) |
25 | { |
26 | ans=tmp.step; |
27 | flag=0; |
28 | return; |
29 | } |
30 | for(int i=0;i<4;i++) |
31 | { |
32 | node a=tmp; |
33 | while(a.x+dx[i]>0&&a.y+dy[i]>0&&a.x+dx[i]<=n&&a.y+dx[i]<=m&&mp[a.x+dx[i]][a.y+dy[i]]=='0'&&(a.x!=t.x||a.y!=t.y)) |
34 | { |
35 | a.x+=dx[i]; |
36 | a.y+=dy[i]; |
37 | } |
38 | a.step++; |
39 | if(a.x==tmp.x&&a.y==tmp.y) |
40 | { |
41 | continue; |
42 | } |
43 | if(vis[a.x][a.y]) |
44 | { |
45 | continue; |
46 | } |
47 | if(a.x==t.x&&a.y==t.y) |
48 | { |
49 | ans=a.step; |
50 | flag=0; |
51 | return; |
52 | } |
53 | q.push(a); |
54 | vis[a.x][a.y]=1; |
55 | } |
56 | } |
57 | } |
58 | int main() |
59 | { |
60 | cin>>n>>m; |
61 | for(int i=1;i<=n;i++) |
62 | { |
63 | for(int j=1;j<=m;j++) |
64 | { |
65 | cin>>mp[i][j]; |
66 | } |
67 | } |
68 | cin>>s.x>>s.y>>t.x>>t.y; |
69 | s.step=0; |
70 | q.push(s); |
71 | vis[s.x][s.y]=1; |
72 | bfs(); |
73 | if(flag) |
74 | { |
75 | cout<<"No!God!Please no!"; |
76 | } |
77 | else |
78 | { |
79 | cout<<ans; |
80 | } |
81 | return 0; |
82 | } |