Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <stdio.h>
- using namespace std;
- struct tCell{long long row, col;};
- queue<tCell> q;
- long long dist[257][257];
- long long n, m, s, t, u, x, y;
- void checker(long long r, long long c, long long prevr, long long prevc)
- {
- if (r<1||r>n||c<1||c>n||dist[r][c]!=0) return;
- q.push({r,c});
- dist[r][c]=dist[prevr][prevc]+1;
- }
- void bfs(tCell start, tCell finish)
- {
- tCell v;
- long long rr,cc;
- dist[start.row][start.col]=1;
- q.push(start);
- while(!q.empty())
- {
- v=q.front();
- q.pop();
- rr=v.row;
- cc=v.col;
- checker(rr-2, cc-1, rr, cc);
- checker(rr-2, cc+1, rr, cc);
- checker(rr+2, cc-1, rr, cc);
- checker(rr+2, cc+1, rr, cc);
- checker(rr-1, cc-2, rr, cc);
- checker(rr-1, cc+2, rr, cc);
- checker(rr+1, cc-2, rr, cc);
- checker(rr+1, cc+2, rr, cc);
- if (dist[finish.row][finish.col]>1) break;
- }
- }
- int main()
- {
- cin>>n>>m;
- cin>>s>>t>>u;
- while(u--)
- {
- cin>>x>>y;
- for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) dist[i][j]=0;
- tCell start = {x, y}, finish = {s, t};
- bfs(start, finish);
- if (dist[s][t]<1) cout<<"-1\n";
- else cout<<dist[s][t]-1<<"\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement