Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int INF = 2e9;
- int R, C, s1, s2, d1, d2;
- int dr[] = {1, 0, -1, 0};
- int dc[] = {0, 1, 0, -1};
- int d[1001][1001];
- bool vis[1001][1001];
- struct cell{
- int r, c;
- };
- bool valid(int r, int c) {
- return r>=0 && r<R && c>=0 && c<C && vis[r][c]==0;
- }
- void Run() {
- vis[0][0] = 1;
- queue<cell>q;
- cell cell1; cell1.r = s1, cell1.c = s2;
- q.push(cell1);
- while((int)q.size()) {
- cell cur = q.front(); q.pop();
- int r = cur.r, c = cur.c;
- for(int i=0; i<4; i++) {
- if(valid(r+dr[i], c+dc[i])) {
- d[r+dr[i]][c+dc[i]] = 1+d[r][c];
- cell to; to.r = r+dr[i], to.c = c+dc[i];
- vis[to.r][to.c] = 1;
- q.push(to);
- }
- }
- }
- cout << d[d1][d2] << "\n";
- }
- int main() {
- while(1) {
- cin >> R >> C;
- if(R==C && R==0) break;
- for(int i=0; i<R; i++)
- for(int j=0; j<C; j++)
- vis[i][j] = d[i][j] = 0;
- int rCnt; cin >> rCnt;
- while(rCnt--) {
- int r; cin >> r;
- int cCnt; cin >> cCnt;
- while(cCnt--) {
- int c; cin >> c;
- vis[r][c] = 1;
- }
- }
- cin >> s1 >> s2 >> d1 >> d2;
- Run();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
