这道题其实只要思考一下就可以轻易解答了
因为没有障碍物等干扰设施,所以这道题目无疑没有你想象的那么难。
这种题目的进阶类型就是给定起点和终点以及障碍物,求最少转弯次数,当然就要用到搜索了,就不会有入门那么简单了。
回到正题
每个矩阵的起点可以自己设定,但是为了转弯次数最少,当然是设在边角上了(理由自己想)。
但这题却绝对不是什么模拟、搜索题,只要掌握其中的规律就可以了。
通过观察样例,发现每个矩阵的最少转弯次数K就是矩阵的长和宽N和M中较少的一个的两倍-2,即写成表达式为2*(min(n,m)-1)
仔细思考一下就会发现:从边角出发,若想使转弯次数最少,就必须得走到尽头再转弯,而转弯次数却和另一条边有关系,设另一条边的长度为X,每走到尽头就要转弯一次并向前走一步再转弯走到尽头······如此循环,就是最容易想到的最简单的最少转弯次数了,到最后一条路时就转了2*(X-1)次弯。易知X越小越好(废话),所以X就是矩阵长和宽中M和N较小的一个了。
代码:
#include<stdio.h>
int t,temp,temp2;
int main()
{
scanf("%d",&t);
while(t--) //多组数据
{
scanf("%d%d",&temp,&temp2);
if(temp<temp2) printf("%d\n",(temp-1)*2); //选择较小的一个按表达式输出
else printf("%d\n",(temp2-1)*2);
}
return 0;
}