POJ_2893_TLE.cpp

#include <iostream>
#include <vector>
using namespace std;

class SlidingPuzzle {
private:
  int inversions(vector<int>& board) {
    int result = 0;
    for (int i = 0; i < board.size(); ++i) {
      for (int k = i + 1; k < board.size(); ++k) {
        if (board[k] < board[i]) {
          ++result;
        }
      }
    }
    return result;
  }
public:
  bool checkSolvablility(vector<int>& board, int n, int m, int zeropos) {
    int inv = inversions(board);
    if (m & 1) {
      return (inv & 1) == 0;
    }
    // even m
    int zeroy = zeropos / m;
    int ydistance = n - zeroy;
    return (inv ^ ydistance) & 1;
  }
};

int main() {
  int n;
  int m;
  cin >> n >> m;
  SlidingPuzzle puzzle;
  while (n != 0 && m != 0) {
    int size = n * m;
    vector<int> board(size - 1);
    int pos = 0;
    int zeropos = 0;
    for (int i = 0; i < size; ++i) {
      int x;
      cin >> x;
      if (x == 0) {
        zeropos = i;
      } else {
        board[pos++] = x;
      }
    }
    bool result = puzzle.checkSolvablility(board, n, m, zeropos);
    cout << (result ? "YES" : "NO") << endl;
    cin >> n >> m;
  }
  return 0;
}