codeforce Direction Change
题目描述
你会得到一个有n行和m列的网格。行和列的编号从1到n,从1到m。第a行和第b列的交点用(a,b)表示。
最初,你站在左上角(1,1)。你的目标是到达右下角(n,m)。
你可以从(a,b)向四个方向移动:向上到(a-1,b),向下到(a+1,b),向左到(a,b-1)或向右到(a,b+1)。
你不能在连续两步棋中向同一方向移动,也不能离开网格。达到(n,m)的最少移动次数是多少?
输入
输入由多个测试案例组成。第一行包含一个整数t(1≤t≤103)–测试案例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数n和m(1≤n,m≤109)–网格的大小。
输出
对于每个测试案例,打印一个单一的整数。如果在给定条件下不可能达到(n,m),则为-1,否则为最小移动次数。
样例
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int t,n,m;
int main()
{
cin>>t;
while(t--){
cin>>n>>m;
if(n<m) swap(n,m);
if(m==1&&n>=3) {
cout<<-1<<endl;
}
else cout<<n*2-2-(n-m)%2<<endl;
}
return 0;
}
数学问题:
先统一n,m,假设n>=m
那么理论上,向下是最优解,要移动 n-1 次,又因为不能重复同一个方向,那就要加别的方向一对一,最后一步不用配对要 n-2 步,总共要 n-3 步
最上角到最右下角,最优解就是向下,向右交替
但是除非n==m,否则最后n=m就停下了
当n=m时,向下向左向下向右可以下降2行,所以跟上面那个一对一其实是符合的,但是剩下的行数必须是偶数,
n-3
不然就不能完成一个循环,那么实际上先循环,到最后只需要向下一步就行,也就是说奇数的比偶数的还要少一步 ,n-2