AtCoder Beginner Contest 170 F - Pond Skater

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define pb push_back
 5 const int maxn =1e6+10;
 6 const int mod=998244353;
 7 string s[maxn];
 8 int h,w,k;
 9 int sx,sy,ex,ey;
10 int xx[5]={58,0,0,1,-1};
11 int yy[5]={58,1,-1,0,0};
12 int ans=-1;
13 struct ac
14 {
15     int x,y,step;
16 };
17 void bfs()
18 {
19     queue<ac>q;
20     s[sx][sy]=‘@‘;
21     q.push({sx,sy,0});
22     while(!q.empty())
23     {
24         ac now=q.front();
25         q.pop();
26         if(now.x==ex&&now.y==ey)
27         {
28             ans=now.step;
29         }
30         for(int i=1;i<=4;i++)
31         {
32             for(int j=0;j<k;j++)
33             {
34                 int tx=xx[i]+now.x;
35                 int ty=yy[i]+now.y;
36                 if(i==1)
37                     ty+=j;
38                 if(i==2)
39                     ty-=j;
40                 if(i==3)
41                     tx+=j;
42                 if(i==4)
43                     tx-=j;
44                 if(tx<0||ty<0||tx>=h||ty>=w||s[tx][ty]==‘@‘)
45                 {
46                    break;
47                 }
48                 s[tx][ty]=‘@‘;
49                  q.push({tx,ty,now.step+1});
50             }
51         }
52     }
53 }
54 
55 int main()
56 {
57     ios::sync_with_stdio(false);
58     cin.tie(0);
59 
60     cin>>h>>w>>k;
61     cin>>sx>>sy>>ex>>ey;
62     sx--,sy--,ex--,ey--;
63     for(int i=0;i<h;i++)
64     {
65         cin>>s[i];
66     }
67     bfs();
68     cout<<ans<<‘\n‘;
69 
70 
71 
72 }

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define pb push_back
 5 const int maxn =1e6+10;
 6 const int mod=1e9+7;
 7 vector<vector<int>>d(maxn);
 8 int h,w,k;
 9 string s[maxn];
10 int sx,sy,ex,ey;
11 int xx[5]={58,0,0,1,-1};
12 int yy[5]={58,1,-1,0,0};
13 
14 void bfs()
15 {
16     queue<pair<int,int>>q;
17     q.push({sx,sy});
18     d[sx][sy]=0;
19     while(!q.empty())
20     {
21         int x=q.front().first;
22         int y=q.front().second;
23         if(x==ex&&y==ey)
24         {
25             return;
26         }
27         q.pop();
28         for(int i=1;i<=4;i++)
29         {
30             for(int j=0;j<k;j++)
31             {
32                 int tx=xx[i]+x;
33                 int ty=yy[i]+y;
34                 if(i==1)
35                     ty+=j;
36                 if(i==2)
37                     ty-=j;
38                 if(i==3)
39                     tx+=j;
40                 if(i==4)
41                     tx-=j;
42                 if(tx<0||ty<0||tx>h-1||ty>w-1||s[tx][ty]==‘@‘||d[tx][ty]<d[x][y]+1)
43                 {
44                     break;
45                 }
46                 if(d[tx][ty]>d[x][y]+1) //同样长的话不能走 否则TLE
47                 {
48                     d[tx][ty]=d[x][y]+1;
49                     q.push({tx,ty});
50                 }
51             }
52         }
53     }
54 }
55 
56 int main()
57 {
58     ios::sync_with_stdio(false);
59     cin.tie(0);
60     cin>>h>>w>>k;
61     cin>>sx>>sy>>ex>>ey;
62     sx--,sy--,ex--,ey--;
63     for(int i=0;i<h;i++)
64         cin>>s[i];
65     int g=1e9;
66     for(int i=0;i<h+5;i++)
67     {
68         for(int j=0;j<w+5;j++)
69         {
70             d[i].pb(g);
71         }
72     }
73     bfs();
74     if(d[ex][ey]==1e9)
75     {
76         cout<<-1<<‘\n‘;
77     }
78     else
79         cout<<d[ex][ey]<<‘\n‘;
80 
81 
82 
83 
84 
85 }