Untitled

public
6shootingstar9 Apr 20, 2025 Never 22
Clone
Plaintext paste1.txt 82 lines (82 loc) | 1.54 KB
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
}