牛客网暑期ACM多校训练营（第八场） E.Touring cities (找规律)

题目链接：https://www.nowcoder.com/acm/contest/146/E

题目大意：给定一个n行m列的棋盘，将格子视为点，相邻的格子对应的点间连一条边。再此基础上新加k条边，形成一个n*m个点的无向图。问经过每个点至少一次的环路长度最短是多少。(n,m>1)

题目思路：我们先画三个图分析，分别为长宽两个奇数，一奇一偶，两个偶数。

我们发现当n和m只要有一个是偶数边的时候我们可以选择为偶数的那一边进行弯折的操作这样可以保证最后经过所有点后可以直接回到(1,1)(1,1)这个时候答案就是n∗mn∗m并且和有没有通道没有关系

当m*n为5*5的时候，答案就是m∗n+1，那么再考虑的就是n和m都为奇数时通道在哪可以优化步数，把n∗m+1优化成n∗m。

如果将棋盘黑白染色，规定左上角的格子是黑色。那么存在哈密尔顿回路的条件是当且仅当新增的边连接了两个不同的黑色格子。

考虑证明：
若没有连接两个不同黑格子的边，那么回路上一个黑格子后必然接一个白格子。
那么回路的黑格子数目一定小于等于白格子数目。但是棋盘上的黑格子数目比白格子多一。矛盾。
若存在一个连接两个不同黑格子的边，那么一定存在一条合法的方案。
两个思路：
1）按照起点终点位置分类讨论构造
2）归纳证明
若有一维大于5，一定可以将其减2
归纳到n,m<=5的情况，此时可以自行验证

#include<bits/stdc++.h>

using namespace std;
const int maxn=100000+100;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m,k;
        bool flag=false;
        scanf("%d%d%d",&n,&m,&k);
        int x1,x2,y1,y2;
        for(int i=0;i<k;i++)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            if(x1==x2&&y1==y2)continue;
            if(x1%2==y1%2&&x2%2==y2%2)flag=true;
        }
        if(n%2==0||m%2==0||flag)
        {
            printf("%d\n",n*m);
        }
        else
        {
            printf("%d\n",n*m+1);
        }
    }
    return 0;
}
/*
11 13 15 17
22 24 26 28
31 33 35 37
*/