E-Touring cities
https://www.nowcoder.com/acm/contest/146/E
给你一个n*m的棋盘，你要从(1,1)出发遍历整个棋盘再回到(1,1),图中某些格子可以直接飞到另一个格子。求最少走多少步回到(1,1)且遍历整个棋盘。
当n*m为偶数的时候（n,m只要有一个为偶数），最短路径为n*m，哈密顿回路。
当n,m均为奇数的时，从（1,1）出发，染为白色，下一个为黑色，相间染色。从（1,1）出发，在（2,1）或（1,2）返回（只有这2种情况），任何一条路径，白色个数不会超过黑色个数（这里的路径是指不重复，每个点只走一次），所以总有一个白色块无法访问，故路径为n*m+1（重复访问一次即可）。但若能从一个白格子飞到另一个白格子即可n*m。
#include<iostream>
using namespace std;
int main()
{int t;cin>>t;while(t--){int n,m,k;cin>>n>>m>>k;int flag=0;int x1,y1,x2,y2;for(int i=0;i<k;i++){cin>>x1>>y1>>x2>>y2;if((x1!=x2||y1!=y2)&&(x1+y1)%2==0&&(x2+y2)%2==0)flag++;}if(n%2==0||m%2==0||flag) cout<<n*m<<endl;else cout<<n*m+1<<endl;}return 0;
}