AOJ1072

Rearranging Seats

■問題
r*cあるものを、それぞれ上下左右に移動させたとき場所がかぶることなく全て移動できるかどうか求める。

■解法
すべてを上下左右に移動できるかどうかは、ある一点から上下左右に移動し、他のすべての点を通って最初の点に戻ってこれるかで判定できる。（全ての点を一本の線でなぞれるかみたいな感じ）
しかし、全探索でやるとO(4^rc)なのできつい。
よく考えると線のなぞり方はr=4,c=3の場合
1 2 3 4
12 9 8 5
11 10 7 6
のようにくねくねさせるとできる。
これはどちらかの辺が偶数なら可能なのでr、cが両方奇数かどうか判定するだけで解ける。
rとcの範囲に騙されそうになった。

■ソース

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
  while(1){
    int r,c;
    cin >> r >> c;
    if(!r && !c) break;
    if(r%2 && c%2){
      cout << "no" << endl;
    }else{
      cout << "yes" << endl;
    }
  }
}