Go to diff to previous submission
#include <cstdio> #include <iostream> #include <queue> using namespace std; int R; // Row count int C; // column count int Gr; // row pos grasshopper int Gc; // column pos grasshopper int Lr; // row pos delicious int Lc; // column pos delicious class Position { public: int first; int second; int hops; Position(int a, int b, int hops = 0) { first = a; second = b; this->hops = hops; } bool operator==(const Position &pos) { if (this->first == pos.first && this->second == pos.second) return true; return false; } }; queue<Position> q; #define boardSize 200 bool board[boardSize][boardSize]; void clearBoard(int xsize, int ysize) { for (int i = 0 ; i < xsize ; ++i) for (int j = 0 ; j < ysize ; ++j) board[i][j] = false; } bool validPos(Position pos) { if (pos.first < 0 || pos.first >= R) return false; if (pos.second < 0 || pos.second >= C) return false; if (board[pos.first][pos.second]) return false; board[pos.first][pos.second] = true; return true; } void generateHops(Position actual) { Position p1 = Position(actual.first-1, actual.second+2, actual.hops+1); Position p2 = Position(actual.first+1, actual.second+2, actual.hops+1); Position p3 = Position(actual.first+2, actual.second+1, actual.hops+1); Position p4 = Position(actual.first+2, actual.second-1, actual.hops+1); Position p5 = Position(actual.first+1, actual.second-2, actual.hops+1); Position p6 = Position(actual.first-1, actual.second-2, actual.hops+1); Position p7 = Position(actual.first-2, actual.second-1, actual.hops+1); Position p8 = Position(actual.first-2, actual.second+1, actual.hops+1); if (validPos(p1)) q.push(p1); if (validPos(p2)) q.push(p2); if (validPos(p3)) q.push(p3); if (validPos(p4)) q.push(p4); if (validPos(p5)) q.push(p5); if (validPos(p6)) q.push(p6); if (validPos(p7)) q.push(p7); if (validPos(p8)) q.push(p8); } int main() { while (true) { cin >> R; if (cin.eof()) break; cin >> C; cin >> Gr; cin >> Gc; cin >> Lr; cin >> Lc; Gr--;Gc--; Lr--;Lc--; Position target = Position(Lr, Lc); clearBoard(R,C); while (!q.empty()) q.pop(); q.push(Position(Gr,Gc)); while (!q.empty()) { Position actual = q.front(); q.pop(); if (actual == target) { cout << actual.hops << endl; q.push(target); break; } generateHops(actual); } if (q.empty()) cout << "impossible" << endl; } return 0; }
--- c4.s662.cteam054.grasshop.cpp.0.grasshop.cpp +++ c4.s686.cteam054.grasshop.cpp.0.grasshop.cpp @@ -37,5 +37,5 @@ queue<Position> q; -#define boardSize 100 +#define boardSize 200 bool board[boardSize][boardSize]; @@ -50,6 +50,4 @@ bool validPos(Position pos) { - - if (pos.first < 0 || pos.first >= R) return false; @@ -61,4 +59,6 @@ return false; + board[pos.first][pos.second] = true; + return true; } @@ -121,5 +121,4 @@ { Position actual = q.front(); - board[actual.first][actual.second] = true; q.pop(); if (actual == target)