Guest User

STL Maps

a guest
Nov 16th, 2012
196
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.17 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <queue>
  4. #include <vector>
  5. #include <map>
  6. using namespace std;
  7. vector <char> x;
  8. vector < vector<char> > y;
  9. short xV[4] = { -2, 0, 2, 0 }, yV[4] = { 0, -2, 0, 2};
  10. struct pos {
  11.     short Hx, Hy, Rx, Ry, depth;
  12.     pos(short Hxx, short Hyy, short Rxx, short Ryy, short ddepth)
  13.     {
  14.         this->depth = ddepth;
  15.         this->Hx = Hxx;
  16.         this->Hy = Hyy;
  17.         this->Rx = Rxx;
  18.         this->Ry = Ryy;
  19.     }
  20.     bool final()
  21.     {
  22.         if (y[Hy][Hx] == 'F' && y[Ry][Rx] == 'F')
  23.             return true;
  24.         return false;
  25.     }
  26.     bool operator==(const pos &a) const // Could be problems with this one
  27.     {
  28.         return (((a.Hx == this->Hx) && (a.Hy == this->Hy)) && ((a.Rx == this->Rx) && (a.Ry == this->Ry)));
  29.     }
  30.     bool operator<(const pos& a) const
  31.     {
  32.         return (a.Hx < this->Hx);
  33.     }
  34. };
  35. bool isReachable(pos a)
  36. {
  37.     if (abs(a.Hx - a.Rx) > 2 || abs(a.Hy - a.Ry) > 2)
  38.         return false;
  39.     return true;
  40. }
  41. void validMoves(queue<pos> &q, pos now, map <pos, bool> visited)
  42. {
  43.     for (int i = 0; i < 4; i++)
  44.     {
  45.         // To set the boundaries... (these are ok)
  46.         bool H = (((now.Hx + xV[i] <= x.size() - 1) && (now.Hx + xV[i] >= 0)) && ((now.Hy + yV[i] <= x.size() - 1) && (now.Hy + yV[i] >= 0)));
  47.         bool R = (((now.Rx + xV[i] <= x.size() - 1) && (now.Rx + xV[i] >= 0)) && ((now.Ry + yV[i] <= x.size() - 1) && (now.Ry + yV[i] >= 0)));
  48.         pos tempH(now.Hx + xV[i], now.Hy + yV[i], now.Rx, now.Ry, now.depth + 1);
  49.         pos tempR(now.Hx, now.Hy, now.Rx + xV[i], now.Ry + yV[i], now.depth + 1);
  50.         cout << (now == tempR) << " (now is not equal to tempR) ";
  51.         cout << (visited[now] == visited[tempR]) <<" - visited[now] is always true, as well as visited[tempR], but the size is: " << visited.size() << "\n";
  52.         //cout << R << " " << tempR.Hx << " " << tempR.Hy << " " << tempR.Rx << " " << tempR.Ry <<"\n";
  53.         if (visited.find(tempH) != visited.end())
  54.             H = false;
  55.         if (visited.find(tempR) != visited.end())
  56.             R = false; // Since visited.find(tempR) is always true, this turns false every time
  57.         // The rest doesn't matter much
  58.         if (xV[i] > 0)
  59.         {
  60.             if (H)
  61.                 if (y[now.Hy][now.Hx + 1] == '.' && isReachable(tempH))
  62.                     q.push(tempH);
  63.             if (R)
  64.                 if (y[now.Ry][now.Rx + 1] == '.' && isReachable(tempR))
  65.                     q.push(tempR);
  66.         }
  67.         if (xV[i] < 0)
  68.         {
  69.             if (H)
  70.                 if (y[now.Hy][now.Hx - 1] == '.' && isReachable(tempH))
  71.                     q.push(tempH);
  72.             if (R)
  73.                 if (y[now.Ry][now.Rx - 1] == '.' && isReachable(tempR))
  74.                     q.push(tempR);
  75.         }
  76.         if (yV[i] > 0)
  77.         {
  78.             if (H)
  79.                 if (y[now.Hy + 1][now.Hx] == '.' && isReachable(tempH))
  80.                     q.push(tempH);
  81.             if (R)
  82.                 if (y[now.Ry + 1][now.Rx] == '.' && isReachable(tempR))
  83.                     q.push(tempR);
  84.         }
  85.         if (yV[i] < 0)
  86.         {
  87.             if (H)
  88.                 if (y[now.Hy - 1][now.Hx] == '.' && isReachable(tempH))
  89.                     q.push(tempH);
  90.             if (R)
  91.                 if (y[now.Ry - 1][now.Rx] == '.' && isReachable(tempR))
  92.                     q.push(tempR);
  93.         }
  94.     }
  95. }
  96. int BFS(pos a)
  97. {
  98.     map <pos, bool> visited;
  99.     queue <pos> q;
  100.     q.push(a);
  101.     visited[q.front()] = true;
  102.     while (!q.empty())
  103.     {
  104.         pos now = q.front();
  105.         visited[now] = true;
  106.         if (now.final())
  107.             return now.depth;
  108.         q.pop();
  109.         validMoves(q, now, visited);
  110.     }
  111.     return 0;
  112. }
  113. void fillAxis(int M)
  114. {
  115.     for (int i = 0; i < M * 2 + 3; i++)
  116.         x.push_back('F');
  117.     y.push_back(x);
  118.     x.clear();
  119. }
  120. int main()
  121. {
  122.     ifstream input("duom.in");
  123.     short N, M, Hx, Hy, Rx, Ry;
  124.     input >> N >> M;
  125.     input >> noskipws;
  126.     fillAxis(M);
  127.     char trash;
  128.     input >> trash;
  129.     for (short i = 0; i < N * 2 + 1; i++)
  130.     {
  131.         x.push_back('F');
  132.         for (short j = 0; j < M * 2 + 1; j++)
  133.         {
  134.             char temp;
  135.             input >> temp;
  136.             x.push_back(temp);
  137.             if (temp == 'H')
  138.             {
  139.                 Hx = j + 1;
  140.                 Hy = i + 1;
  141.             }
  142.             if (temp == 'R')
  143.             {
  144.                 Rx = j + 1;
  145.                 Ry = i + 1;
  146.             }
  147.         }
  148.         input >> trash;
  149.         x.push_back('F');
  150.         y.push_back(x);
  151.         x.clear();
  152.     }
  153.     input.close();
  154.     fillAxis(M);
  155.     pos a(Hx, Hy, Rx, Ry, 0);
  156.     int ans = BFS(a);
  157.     if (ans == 0)
  158.         cout <<"Mirtis\n";
  159.     else
  160.         cout << ans << "\n";
  161.     ofstream output("duom.out");
  162.     if (ans == 0)
  163.         output <<"Mirtis\n";
  164.     else
  165.         output << ans << "\n";
  166.     for (int i = 0; i < N * 2 + 3; i++)
  167.     {
  168.         for (int j = 0; j < M * 2 + 3; j++)
  169.             output << y[i][j];
  170.         output << "\n";
  171.     }
  172.     output.close();
  173.     cin >> ans;
  174.     return 0;
  175. }
Advertisement
Add Comment
Please, Sign In to add comment