Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <queue>
- #include <vector>
- #include <map>
- using namespace std;
- vector <char> x;
- vector < vector<char> > y;
- short xV[4] = { -2, 0, 2, 0 }, yV[4] = { 0, -2, 0, 2};
- struct pos {
- short Hx, Hy, Rx, Ry, depth;
- pos(short Hxx, short Hyy, short Rxx, short Ryy, short ddepth)
- {
- this->depth = ddepth;
- this->Hx = Hxx;
- this->Hy = Hyy;
- this->Rx = Rxx;
- this->Ry = Ryy;
- }
- bool final()
- {
- if (y[Hy][Hx] == 'F' && y[Ry][Rx] == 'F')
- return true;
- return false;
- }
- bool operator==(const pos &a) const // Could be problems with this one
- {
- return (((a.Hx == this->Hx) && (a.Hy == this->Hy)) && ((a.Rx == this->Rx) && (a.Ry == this->Ry)));
- }
- bool operator<(const pos& a) const
- {
- return (a.Hx < this->Hx);
- }
- };
- bool isReachable(pos a)
- {
- if (abs(a.Hx - a.Rx) > 2 || abs(a.Hy - a.Ry) > 2)
- return false;
- return true;
- }
- void validMoves(queue<pos> &q, pos now, map <pos, bool> visited)
- {
- for (int i = 0; i < 4; i++)
- {
- // To set the boundaries... (these are ok)
- 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)));
- 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)));
- pos tempH(now.Hx + xV[i], now.Hy + yV[i], now.Rx, now.Ry, now.depth + 1);
- pos tempR(now.Hx, now.Hy, now.Rx + xV[i], now.Ry + yV[i], now.depth + 1);
- cout << (now == tempR) << " (now is not equal to tempR) ";
- cout << (visited[now] == visited[tempR]) <<" - visited[now] is always true, as well as visited[tempR], but the size is: " << visited.size() << "\n";
- //cout << R << " " << tempR.Hx << " " << tempR.Hy << " " << tempR.Rx << " " << tempR.Ry <<"\n";
- if (visited.find(tempH) != visited.end())
- H = false;
- if (visited.find(tempR) != visited.end())
- R = false; // Since visited.find(tempR) is always true, this turns false every time
- // The rest doesn't matter much
- if (xV[i] > 0)
- {
- if (H)
- if (y[now.Hy][now.Hx + 1] == '.' && isReachable(tempH))
- q.push(tempH);
- if (R)
- if (y[now.Ry][now.Rx + 1] == '.' && isReachable(tempR))
- q.push(tempR);
- }
- if (xV[i] < 0)
- {
- if (H)
- if (y[now.Hy][now.Hx - 1] == '.' && isReachable(tempH))
- q.push(tempH);
- if (R)
- if (y[now.Ry][now.Rx - 1] == '.' && isReachable(tempR))
- q.push(tempR);
- }
- if (yV[i] > 0)
- {
- if (H)
- if (y[now.Hy + 1][now.Hx] == '.' && isReachable(tempH))
- q.push(tempH);
- if (R)
- if (y[now.Ry + 1][now.Rx] == '.' && isReachable(tempR))
- q.push(tempR);
- }
- if (yV[i] < 0)
- {
- if (H)
- if (y[now.Hy - 1][now.Hx] == '.' && isReachable(tempH))
- q.push(tempH);
- if (R)
- if (y[now.Ry - 1][now.Rx] == '.' && isReachable(tempR))
- q.push(tempR);
- }
- }
- }
- int BFS(pos a)
- {
- map <pos, bool> visited;
- queue <pos> q;
- q.push(a);
- visited[q.front()] = true;
- while (!q.empty())
- {
- pos now = q.front();
- visited[now] = true;
- if (now.final())
- return now.depth;
- q.pop();
- validMoves(q, now, visited);
- }
- return 0;
- }
- void fillAxis(int M)
- {
- for (int i = 0; i < M * 2 + 3; i++)
- x.push_back('F');
- y.push_back(x);
- x.clear();
- }
- int main()
- {
- ifstream input("duom.in");
- short N, M, Hx, Hy, Rx, Ry;
- input >> N >> M;
- input >> noskipws;
- fillAxis(M);
- char trash;
- input >> trash;
- for (short i = 0; i < N * 2 + 1; i++)
- {
- x.push_back('F');
- for (short j = 0; j < M * 2 + 1; j++)
- {
- char temp;
- input >> temp;
- x.push_back(temp);
- if (temp == 'H')
- {
- Hx = j + 1;
- Hy = i + 1;
- }
- if (temp == 'R')
- {
- Rx = j + 1;
- Ry = i + 1;
- }
- }
- input >> trash;
- x.push_back('F');
- y.push_back(x);
- x.clear();
- }
- input.close();
- fillAxis(M);
- pos a(Hx, Hy, Rx, Ry, 0);
- int ans = BFS(a);
- if (ans == 0)
- cout <<"Mirtis\n";
- else
- cout << ans << "\n";
- ofstream output("duom.out");
- if (ans == 0)
- output <<"Mirtis\n";
- else
- output << ans << "\n";
- for (int i = 0; i < N * 2 + 3; i++)
- {
- for (int j = 0; j < M * 2 + 3; j++)
- output << y[i][j];
- output << "\n";
- }
- output.close();
- cin >> ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment