#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; class Position { public: Position(int x, int y, int n) : m_x(x) , m_y(y) , m_n(n) , m_maxIndex(n*n) { m_index = m_x * m_n + m_y; } Position(int offsetx, int offsety, const Position& other) : m_x(other.m_x + offsetx) , m_y(other.m_y + offsety) , m_n(other.m_n) , m_maxIndex(other.m_maxIndex) { m_index = m_x * m_n + m_y; } bool isDestination() const { if (m_index == m_maxIndex -1) { return true; } return false; } bool isValid() const { if (m_index < 0) { return false; } if (m_index >= m_maxIndex) { return false; } if (m_x < 0 || m_x >= m_n) { return false; } if (m_y < 0 || m_y >= m_n) { return false; } return true; } int getPosition() const { return m_index; } int m_x; int m_y; int m_n; int m_index; const int m_maxIndex; }; ostream& operator<<(ostream& os, const Position& pos) { os << "Pos[" << pos.m_x << "," << pos.m_y; if (!pos.isValid()) { os << " not-valid"; } os << "]"; return os; } class State { public: State(int n); // initial state State(const State& orig); // initial state bool addPosition(const Position& pos); bool sawPosition(const Position& pos) const; const int m_n; std::vector m_previousPositions; unsigned int m_previousMoves; void dump(ostream& os) const; }; void State::dump(ostream& os) const { os << "State: n=" << m_n << ", moves=" << m_previousMoves << "["; for (int i = 0; i < m_previousPositions.size(); ++i) { if (i > 0) { os << " "; } if (m_previousPositions.at(i)) { os << "1"; } else { os << " "; } } os << "]"; } inline ostream& operator<<(ostream& os, const State& state) { state.dump(os); return os; } State::State(int n) : m_n(n) , m_previousMoves(0) { m_previousPositions.resize(n * n); // all should be false } State::State(const State& orig) : m_n(orig.m_n) , m_previousPositions(orig.m_previousPositions) , m_previousMoves(orig.m_previousMoves) { // } // return true if the new position already existed in state bool State::addPosition(const Position& pos) { int index = pos.getPosition(); assert(index >= 0 && index < m_previousPositions.size()); if (m_previousPositions.at(index)) { return true; } m_previousPositions.at(index) = true; ++m_previousMoves; return false; } bool State::sawPosition(const Position& pos) const { int index = pos.getPosition(); assert(index >= 0 && index < m_previousPositions.size()); return m_previousPositions.at(index); } class Task { public: Task(const Position& position, std::shared_ptr& state_sp) : m_pos(position) , m_state_sp(state_sp) { } Position m_pos; std::shared_ptr m_state_sp; }; int countMoves(int n, int i, int j) { // given n-by-n board // compute count for knight[i,j] // from 0,0 to n-1,n-1 int delta_x[8]; int delta_y[8]; queue tasks; std::shared_ptr initialState_sp = std::make_shared(n); tasks.push(Task(Position(0, 0, n), initialState_sp)); State checkedPositions(n); int index = 0; delta_x[index ] = i; delta_y[index++] = j; delta_x[index ] = i; delta_y[index++] = -j; delta_x[index ] = -i; delta_y[index++] = j; delta_x[index ] = -i; delta_y[index++] = -j; assert(index == 4); if (i != j) { delta_x[index ] = j; delta_y[index++] = i; delta_x[index ] = j; delta_y[index++] = -i; delta_x[index ] = -j; delta_y[index++] = i; delta_x[index ] = -j; delta_y[index++] = -i; assert(index == 8); } int count = -1; //cerr << "\n\n"; //cerr << "countMoves(" << n << ", i=" << i << ", j=" << j << ")" << endl; while (tasks.size() > 0) { //cerr << "Task:" << endl; //cerr << " tasks.size() = " << tasks.size() << endl; Task currentTask = tasks.front(); tasks.pop(); std::shared_ptr newState = currentTask.m_state_sp; Position pos = currentTask.m_pos; //cerr << " lastState = " << newState << endl; //cerr << " pos = " << pos << endl; if (pos.isDestination()) { //cerr << "found destination here!" << endl; count = newState->m_previousMoves; break; } if (checkedPositions.addPosition(pos)) { continue; } newState = std::make_shared(*newState.get()); if (newState->addPosition(pos)) { // already saw newPos //cerr << " already say pos [" << pos.m_x << "," << pos.m_y << "]" << endl; continue; } //cerr << " newState = " << newState << endl; for (int i = 0; i < index; ++i) { Position nextPos( delta_x[i], delta_y[i], pos); //cerr << " i = " << i << ", dx=" << delta_x[i] << ", dy=" << delta_y[i] << ", nextPos = " << nextPos << endl; if (! nextPos.isValid()) { continue; } if ( nextPos.isDestination() ) { //cerr << "found destination" << endl; count = newState->m_previousMoves; break; } if (checkedPositions.sawPosition(nextPos)) { continue; } if (!newState->sawPosition(nextPos) ) { //cerr << " pushing nextPos = " << nextPos << endl; tasks.push(Task(nextPos, newState)); } } if (count > 0) { break; } //cerr << " bottom of loop" << endl; } if (count < 0) { //cerr << "not found" << endl << endl; return count; } //cerr << "found" << endl << endl; return count; } int main(){ int n; cin >> n; // your code goes here int cached_values[n+1][n+1]; int limit; if ((n % 2) == 0) { limit = n/2 + 1; } else { limit = n/2; } for (int i = 1; i < n; ++i) { for (int j = 1; j < i; ++j) { int count = cached_values[j][i]; //cerr << "cached for " << i << "," << j << " = " << count << endl; if (j > 1) { cout << " "; } cout << count; } for (int j = i; j < n; ++j) { int count = -2; if (i > limit && j > limit) { if (i == (n - 1) && j == (n - 1)) { count = 1; } else { count = -1; } } else { if (i == j && ((n - 1) % i) == 0) { count = (n-1) / i; } } if (count == -2) { count = countMoves(n, i, j); } cached_values[i][j] = count; //cerr << "cachint for " << i << "," << j << " = " << count << endl; if (j > 1) { cout << " "; } cout << count; } cout << "\n"; } return 0; }