【蓝桥杯05】：小明每天都要练功，练功中的重要—项是梅花桩。小明练功的梅花桩排列成n行m列，相邻两行的距离为1，相邻两列的距离也为；小明想知道，在不掉下梅花桩的情况下，自己最少要多少步可以移动到目标。

小半 • 2023年1月12日下午2:15 • 硬件开发 • 阅读 203

问题描述：

小明每天都要练功，练功中的重要一项是梅花桩。

小明练功的梅花桩排列成n行m列，相邻两行的距离为1，相邻两列的距离也为1。

小明站在第1行第1列上，他要走到第n行第m列上。小明已经练了一段时间，他现在可以—步移动不超过d的距离(直线距离)。
小明想知道，在不掉下梅花桩的情况下，自己最少要多少步可以移动到目标。

输入格式：

输入的第一行包含两个整数n, m，分别表示梅花桩的行数和列数。
第二行包含一个实数d(最多包含—位小数)，表示小明一步可以移动的距离。

输出格式：

输出一个整数，表示小明最少多少步可以到达目标。

样例输入：

3 4

1.5

样例输出：

评测用例规模与约定

        对于 30% 的评测用例，2 <= n, m <= 20，1 <= d <= 20。
        对于 60% 的评测用例，2 <= n, m <= 100，1 <= d <= 100。
        对于所有评测用例，2 <= n, m <= 1000，1 <= d <= 100。

个人思路：

BFS算法（广度优先遍历）

1.一种是直线寻找最短

2.斜线寻找最短

C语言解决:

小明每天都要练功，练功中的重要一项是梅花桩。小明练功的梅花桩排列成n行m列，相邻两行的距离为1，相邻两列的距离也为1。小明站在第1行第1列上，他要走到第n行第m列上。小明已经练了一段时间，他现在可以—步移动不超过d的距离(直线距离)。
小明想知道，在不掉下梅花桩的情况下，自己最少要多少步可以移动到目标。

//小明想知道，在不掉下梅花桩的情况下，自己最少要多少步可以移动到目标。
#include <stdio.h>
#include <math.h>
int main(){
	int n,m,i,j;
	int b=0;//最少走几步 
	int z=0;//斜着能走的行列数
	double x=sqrt(2);
	float d;
	scanf("%d %d",&n,&m);//第一行输入 行数列数
	scanf("%f",&d);
	int dd=(int)d;
	
	for(i=0;i<=1000;i++){
		if(d>x){
			x+=x;
		}
		else{
			z=i-1;
			break;
		}
	}
	for(i=1,j=1;(i<=n)&&(j<=m);i++,j++){
		if(n==i && m==j)
			break;
		if(n==i){
			b+=((m-j)/dd)+((m-j)%dd);
			break;
		} 
    	if(m==j){
     		b+=((n-i)/dd)+((n-i)%dd);
     		break;
    	}
    	if((n-i>=z)&&(m-j>=z)){
     		i+=z;
     		j+=z;
     		b++;
    	}else if((n-i<z)&&(m-j>=z)){
     		i+=(n-i);
     		j+=(n-i);
     		b++;
    	}else if((n-i>=z)&&(m-j<z)){
     		i+=(m-j);
     		j+=(m-j);
     		b++;
    	}
	}
	printf("%d\n",b);
	return 0;	
}

运行结果示例：

Java解决：

小明每天都要练功，练功中的重要一项是梅花桩。小明练功的梅花桩排列成n行m列，相邻两行的距离为1，相邻两列的距离也为1。小明站在第1行第1列上，他要走到第n行第m列上。小明已经练了一段时间，他现在可以—步移动不超过d的距离(直线距离)。
小明想知道，在不掉下梅花桩的情况下，自己最少要多少步可以移动到目标。

package lanqiao;
import java.util.Scanner;
public class Test {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        double d=sc.nextDouble();
        int c=(int)d;
        int step=0,z=0,i,j;
        double x=Math.sqrt(2);
        for (i = 1; i <=1000; i++) {
            if(d>x){
                x+=x;
            }else{
                z=i-1;
                break;
            }
        }
        for (i=1,j = 1; i<=n&j<=m;) {
            if(n==i&&m==j)break;
            if(n==i){
                step+=((m-j)/c)+((m-j)%c);
                break;
            }
            if(m==j){
                step+=((n-i)/c)+((n-i)%c);
                break;
            }
            if(n-i>=z&&m-j>=z){
                i+=z;
                j+=z;
                step++;
            }else if(n-i<z&&m-j>=z){
                i+=(n-i);
                j+=(n-i);
                step++;
            }else if(n-i>=z&&m-j<z){
                i+=(m-j);
                j+=(m-j);
                step++;
            }
        }
        System.out.println(step);
    }
}

运行结果示例：