送外卖(PAT)

1.题目描述

冬天到了，小伙伴们都懒得出去吃饭了，纷纷打电话叫起了外卖。送外卖的小哥想找出一条最短的路径，小区门口进来，送完外卖又回到小区门口。
整个小区是一个由m*n个边长为1的正方形组成的矩形，各幢公寓楼分布于正方型的顶点上，小区门口位于左上角。每幢楼与相邻的八个方向的楼之间都有道路。
下图为m=2，n=3的小区地图，并且外卖小哥要经过的最短路径为6。

2.输入描述:

输入有多组数据。
每组数据包含两个整数m (2≤n≤2^128) 和n (2≤r≤2^128)，分别代表行数和列数。

3.输出描述:

对应每一组数据，输出外卖小哥需要经过的最短路径。结果保留两位小数。

4.输入例子:

2 2
3 3

5.输出例子:

4.00
9.41

6.解题思路：

1、根据题意，简单的理解就是给出一个二维矩阵点，然后求出以最短的路径把每个点走一遍
2、首先我们注意的是题目给出的两个整数的范围非常大，所以仅仅是int肯定是不行的，这就要用字符串来进行大数运算
3、大数运算：

（1）先将两个字符串的每一位转换为整数并按照乘法的规则依次相乘
（2）将得到的整数存储在一个整数数组中
（3）每一个大于10的数都会产生进位，最后取余可得出准确的每一位数
（4）因为整数数组与真实的大数是相反的，所以数组末尾的0，也就是个位数之前的0是多余的，需要移动数组下标，保证输出不会出现多余的0

4、最后根据矩阵是否为奇数或者偶数，如果是偶数，那么快递员的最短路径就是矩点的个数，如果是奇数，有一步一定是走对角线的，也就是根号2的距离（≈1.41），也就是矩点数减一加根号2.

7.源代码：

#include<stdio.h>
#include<string.h>
#define N 100
int main()
{
	char m[N],n[N];
	while(scanf("%s %s",m,n)!=-1)
	{
		int i,j,L[N];
		int len1=strlen(m);
		int len2=strlen(n);
		memset(L,0,sizeof(L));
		for(i=0;i<len1;i++)
			for(j=0;j<len2;j++)
				L[i+j]+=(m[len1-i-1]-'0')*(n[len2-j-1]-'0');//乘运算
		for(i=0;i<len1+len2;i++)
			if(L[i]>=10)
			{
				L[i+1]+=L[i]/10;//进位
				L[i]%=10;//取余
			}
		while(L[i]==0)//去零
			i--;
		while(i>=0)
			printf("%d",L[i--]);
		if(m[len1-1]%2==0||n[len2-1]%2==0)
			printf(".00\n");
		else
			printf(".41\n");	
	}
	return 0;
}