daily pastebin goal
4%
SHARE
TWEET

asewdew

a guest Oct 12th, 2017 44 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <deque>
  3. #include <stdio.h>
  4. #include <string>
  5. using namespace::std;
  6. const int N = 505;
  7. char tab[N][N];
  8. int n, m, rezult = N * N, ruch_x[] = {0, 1, 0, -1}, ruch_y[] = {1, 0, -1, 0};
  9. pair<int, int> delta, start, meta;
  10. struct dana { int x, y, dx, dy, wynik; };
  11. deque<dana> kolejka;
  12. bool zlewa[N][N], zprawa[N][N], zdolu[N][N], zgory[N][N];
  13. bool mozna(int x1, int y1, int x2, int y2) {
  14.     x1 *= 2; y1 *= 2; x2 *= 2; y2 *= 2;
  15.     if(x1 < 1 || x2 < 1 || x1 > 2 * m+1 || x2 > 2 * m + 1 || y1 < 1 || y2 < 1 || y1 > 2 * n +1 || y2 > 2 * n + 1) return false;
  16.     if(tab[(x1+x2)/2][(y1+y2)/2] == '.') return true;
  17.     return false;
  18. }
  19. bool wchodze(int x, int y, int dx, int dy) {
  20.     if(dx > 0 && zlewa[x+dx][y+dy]) return false;
  21.     if(dx < 0 && zprawa[x+dx][y+dy]) return false;
  22.     if(dy > 0 && zdolu[x+dx][y+dy]) return false;
  23.     if(dy < 0 && zgory[x+dx][y+dy]) return false;
  24.     return true;
  25. }
  26. pair<int, int> prawo() {
  27.     if(delta.first > 0) return make_pair(0, -1);
  28.     if(delta.first < 0) return make_pair(0, 1);
  29.     if(delta.second > 0) return make_pair(1, 0);
  30.     if(delta.second < 0) return make_pair(-1, 0);
  31. }
  32. int dupa = 0;
  33. void DFS(int x, int y, int w) {
  34.     //if(dupa > 50) return;
  35.     if(delta.first > 0) {
  36.             if(zlewa[x][y]) return;
  37.     }
  38.     else if(delta.first < 0) {
  39.         if(zprawa[x][y]) return;
  40.     }
  41.     else if(delta.second > 0) {
  42.         if(zdolu[x][y]) return;
  43.     }
  44.     else if(delta.second < 0) {
  45.         if(zgory[x][y]) return;
  46.     }
  47.    
  48.     //cout << x << " " << y << " " << delta.first << " " << delta.second << " ";
  49.    
  50.     if(delta.first > 0) {
  51.             zlewa[x][y] = true;
  52.             //cout << "z lewa";
  53.     }
  54.     else if(delta.first < 0) {
  55.         zprawa[x][y] = true;
  56.         //cout << "z prawa";
  57.     }
  58.     else if(delta.second > 0) {
  59.             zdolu[x][y] = true;
  60.             //cout << "z dolu";
  61.     }
  62.     else if(delta.second < 0) {
  63.             zgory[x][y] = true;
  64.             //cout << "z gory";
  65.     }
  66.     //cout << endl;
  67.     //dupa++;
  68.     if(x==meta.first && y==meta.second) {
  69.         rezult = min(rezult, w);
  70.         //cout << "WWWWWW: " << w << endl;
  71.     }
  72.     //if(x==3 && y == 2) cout << "MAM: " << w << endl;
  73.     pair<int, int> d_prawo = prawo();
  74.     if(mozna(x, y, x+delta.first, y + delta.second)) {
  75.         if(wchodze(x, y, delta.first, delta.second)) DFS(x+delta.first, y+delta.second, w);
  76.         //if(x==5 && y==5)
  77.         //cout << "DUPA: " << x << " " << y << " " << delta.first << " " << delta.second << endl;
  78.     } else if(mozna(x, y, x+d_prawo.first, y+d_prawo.second)) {
  79.         delta = {d_prawo.first, d_prawo.second};
  80.         if(wchodze(x, y, delta.first, delta.second)) DFS(x+d_prawo.first, y+d_prawo.second, w);
  81.     }
  82.     else if(mozna(x, y, x-d_prawo.first, y-d_prawo.second)) {
  83.         delta = {-d_prawo.first, -d_prawo.second};
  84.         if(wchodze(x, y, delta.first, delta.second)) DFS(x+delta.first, y+delta.second, w);
  85.     }
  86.     else if(mozna(x, y, x-delta.first, y-delta.second)) {
  87.         delta.first *= -1;
  88.         delta.second *= -1;
  89.         if(wchodze(x, y, delta.first, delta.second)) DFS(x+delta.first, y+delta.second, w);
  90.     }
  91.     for(int i = 0; i < 4; i++) {
  92.         if(mozna(x, y, x+ruch_x[i], y+ruch_y[i]) && wchodze(x, y, ruch_x[i], ruch_y[i]))
  93.             kolejka.push_back({x+ruch_x[i], y+ruch_y[i], ruch_x[i], ruch_y[i], w+1});
  94.     }
  95. }
  96. bool odwiedzony[N][N];
  97. void dfs(int x, int y) {
  98.     odwiedzony[x][y] = true;
  99.     for(int i = 0; i < 4; i++)
  100.         if(mozna(x, y, x+ruch_x[i], y+ruch_y[i]) && !odwiedzony[x+ruch_x[i]][y+ruch_y[i]]) dfs(x+ruch_x[i], y+ruch_y[i]);
  101. }
  102. string strona = "";
  103. //string numer = "5";
  104. int main() {
  105.     //freopen("Rakieta/90.in", "r", stdin);
  106.     cin >> n >> m >> strona;
  107.     for(int i = 2*n+1; i >= 1; i--) {
  108.         string wiersz;
  109.         cin >> wiersz;
  110.         for(int j = 0; j < 2 * m + 1; j++) {
  111.             tab[j+1][i] = wiersz[j];
  112.             if(tab[j+1][i] == 'S') {
  113.                 start = {(j+1)/2, i/2};
  114.                 tab[j+1][i] = '.';
  115.             } else if(tab[j+1][i] == 'R') {
  116.                 meta = {(j+1)/2, i/2};
  117.                 tab[j+1][i] = '.';
  118.             }
  119.         }  
  120.     }
  121.     //cout << start.first << " " << start.second << endl;
  122.     //cout << n << " " << m << endl;
  123.     if(strona=="GORA") delta = {0, 1};
  124.     else if(strona == "PRAWO") delta = {1, 0};
  125.     else if(strona == "DOL") delta = {0, -1};
  126.     else if(strona == "LEWO") delta = {-1, 0};
  127.    
  128.     dfs(start.first, start.second);
  129.     if(!odwiedzony[meta.first][meta.second]) {
  130.         cout << "-1";
  131.         return 0;
  132.     }
  133.        
  134.     kolejka.push_back({start.first, start.second, delta.first, delta.second, 0});
  135.     //kolejka.push_back({3, 3, -1, 0, 1});
  136.     //kolejka.push_back({3, 4, 1, 0, 0});
  137.     //kolejka.push_back({3, 5, 0, -1, 0});
  138.     while(!kolejka.empty()) {
  139.         //cout << "Start: " << kolejka.front().x << " " << kolejka.front().y << " " << kolejka.front().dx << " " << kolejka.front().dy << " " << kolejka.front().wynik << endl;
  140.         delta = {kolejka.front().dx, kolejka.front().dy};
  141.         DFS(kolejka.front().x, kolejka.front().y, kolejka.front().wynik);
  142.         kolejka.pop_front();
  143.         //cout << endl;
  144.     }
  145.     //cout << "DUPA: " << dupa << endl;
  146.     cout << rezult;
  147.     //delta = {1, 0};
  148.     //DFS(3, 4);
  149.     /*for(int y = 2 * n + 1; y >= 1; y--) {
  150.         for(int x = 1; x <= 2 *m+1; x++) cout << tab[x][y];
  151.         cout << endl;
  152.     }
  153.     while(true) {
  154.         int x1, y1, x2, y2;
  155.         cin >> x1 >> y1 >> x2 >> y2;
  156.         cout << mozna(x1, y1, x2, y2) << endl;
  157.     }*/
  158. }
RAW Paste Data
Top