SHARE
TWEET

Untitled

a guest Jun 17th, 2019 45 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define MAX 101
  3. #define pb push_back
  4. #define pc putchar
  5. #define gc getchar
  6. #define FOR(i, n) for(;i<n;i++)
  7. #define mm(a, n) memset(a, n, sizeof(a))
  8. #define ini1(a) scanf("%d", &a)
  9. #define ini2(a, b) ini1(a); ini1(b);
  10. #define ini3(a, b, c) ini2(a, b); ini1(c);
  11. #define ini4(a, b, c, d) ini3(a, b, c); ini1(d);
  12. #define VALID(a) (a.r<r)&&(a.r>=0)&&(a.c<c)&&(a.c>=0)
  13. #define REST(a) rest[a.r][a.c]
  14. #define VIS(a) vis[a.r][a.c][a.l]
  15. using namespace std;
  16.  
  17. typedef struct {int r, c, l;} State;
  18. typedef struct {int od[4];} Dir;
  19.  
  20. int r, c, rest[MAX][MAX], vis[MAX][MAX][MAX];
  21.  
  22. Dir openDir[MAX][MAX]; //Holds the left, right, up, down open direction
  23.  
  24. int main()
  25. {
  26.     #ifndef ONLINE_JUDGE
  27.     freopen("input.txt", "r", stdin);
  28.     freopen("output.txt", "w", stdout);
  29.     #else
  30.     #endif
  31.     while(scanf("%d %d", &r, &c)!=EOF)
  32.     {
  33.         int i=0, n; ini1(n);
  34.         mm(rest, 0);
  35.         memset(&openDir, 0, sizeof openDir); //EXprecting to work
  36.         FOR(i, n)
  37.         {
  38.             State a, b;
  39.             ini4(a.r, a.c, b.r, b.c);
  40.             if(a.r==b.r)
  41.             {
  42.                 int k=min(a.c, b.c), j=max(a.c, b.c);
  43.                 openDir[a.r][k++]={0, 0, 1, 0};
  44.                 FOR(k, j)
  45.                 {
  46.                     openDir[a.r][k]={0, 0, 1, 1};
  47.                 }
  48.                 openDir[a.r][k]={0, 0, 0, 1};
  49.             }
  50.             else if(a.c==b.c)
  51.            {
  52.                int k=min(a.r, b.r), j=max(a.r, b.r);
  53.                openDir[k++][a.c]={1, 0, 0, 0};
  54.                FOR(k, j)
  55.                {
  56.                    openDir[k][a.c]={1, 1, 0, 0};
  57.                }
  58.                openDir[k][a.c]={0, 1, 0, 0};
  59.            }          
  60.        }
  61.        
  62.        mm(vis, 0);
  63.        ini1(n);
  64.        
  65.        i=0; FOR(i, n)
  66.        {
  67.            State x;
  68.            ini3(x.l, x.r, x.c);
  69.            
  70.            vis[x.r][x.c][x.l]=1;
  71.            //VIS(x)=1;
  72.            //printf("Input: (%d, %d, %d)\n", x.r, x.c, x.l);
  73.            
  74.        }
  75.        //printf(" VIS(adx)=%d\n", vis[2][1][4] );
  76.        State src={0, 0, 0};
  77.        REST(src)=1;
  78.        queue<State> q;  q.push(src);
  79.        while(!q.empty())
  80.        {
  81.                   //printf(" VIS(adx)=%d\n", vis[2][1][4] );
  82.             src=q.front(); q.pop();
  83.             if((src.r==r-1)&&(src.c==c-1))
  84.             {
  85.                  printf("%d\n", src.l);
  86.                  break;
  87.             }
  88.              
  89.             //printf("From (%d, %d)\n", src.r, src.c);
  90.              
  91.             int dr[]={1, -1, 0, 0};
  92.             int dc[]={0, 0, 1, -1};
  93.             int k=0; FOR(k, 4)
  94.             {
  95.                 if(openDir[src.r][src.c].od[k]==0) //0 means open
  96.                 {
  97.                     State t={src.r+dr[k], src.c+dc[k], src.l+1};
  98.                     if(VALID(t))
  99.                     {
  100.                         if(!REST(t))
  101.                         {
  102.                             //printf("  To (%d, %d) and time %d\n", t.r, t.c, t.l);
  103.                             //printf("  VIS(%d, %d)=%d\n", t.r, t.c, vis[t.r][t.c][t.l]);
  104.                            
  105.                             if(VIS(t)==0)
  106.                             {      
  107.                                 q.push(t);
  108.                                 REST(t)=1;
  109.                             }
  110.                             else
  111.                             {
  112.                                 t.l++;
  113.                                 q.push(t);
  114.                                 REST(t)=1;
  115.                             }
  116.                         }
  117.                     }
  118.                 }
  119.             }
  120.        }
  121.     }
  122.     return 0;
  123. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top