UVa-solutions/10653.cpp at master · amitpriyankar/UVa-solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
struct cord{
    int x;
    int y;
};
int main()
{
    while(true)
    {
        int r,c;
        cin>>r>>c;
        if(r==0&&c==0)return 0;
        bool ok[r][c];
        memset(ok,true,sizeof(ok));
        int k;
        cin>>k;
        while(k--)
        {
            int rval;
            cin>>rval;
            int ct,val;
            cin>>ct;
            while(ct--)
            {
                cin>>val;
                ok[rval][val]=false;
            }
        }
        int ix,iy,fx,fy;
        cin>>ix>>iy>>fx>>fy;
        queue<struct cord> q;
        struct cord init;
        init.x=ix,init.y=iy;
        int dis[r][c];
        memset(dis,0,sizeof(dis));
        q.push(init);
        while(!q.empty())
            {
                struct cord amit;
                amit=q.front();
                q.pop();
                int curx=amit.x;
                int cury=amit.y;
                for(int i=-1; i<=1; i++)
                {
                    for(int j=-1; j<=1; j++)
                {
                    if(abs(i)!=abs(j))
                    {
                    if(curx+i==r||(curx+i<0)||cury+j==c||(cury+j<0))continue;
                    if(ok[curx+i][cury+j])
                    {
                        ok[curx+i][cury+j]=false;
                    struct cord temp;
                    temp.x=curx+i;
                    temp.y=cury+j;
                    q.push(temp);
                    dis[curx+i][cury+j]=1+dis[curx][cury];
                    if(curx+i==fx&&cury+j==fy)
                    {
                        cout<<dis[curx+i][cury+j]<<endl;
                        break;
                    }
                    }
                    }
                }

                }
            }

    }
}