首页 > 试题广场 >

小红走网格

[编程题]小红走网格

热度指数：3399 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 1024M，其他语言2048M
算法知识视频讲解

$\hspace{15pt}$ 在二维平面坐标系中，小红初始位置为 $(0, 0)$ 。她可以向四个方向移动，移动的步数由四个正整数 $a$ 、 $b$ 、 $c$ 、 $d$ 定义，分别表示小红向上、向下、向左和向右移动一次的步数。
$\hspace{23pt}\bullet\,$ 向上移动一次，走 $a$ 步： $(0, 0) \to (0, a)$ ；
$\hspace{23pt}\bullet\,$ 向下移动一次，走 $b$ 步： $(0, 0) \to (0, -b)$ ；
$\hspace{23pt}\bullet\,$ 向左移动一次，走 $c$ 步： $(0, 0) \to (-c, 0)$ ；
$\hspace{23pt}\bullet\,$ 向右移动一次，走 $d$ 步： $(0, 0) \to (d, 0)$ 。
$\hspace{15pt}$ 小红最终想要到达的目标位置为 $(x,y)$ 。请判断小红是否可以通过上述步数到达目标位置。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
在一行上输入六个整数  代表目标位置所在坐标、向上下左右四个方向单次移动的步数。

输出描述:

对于每一组测试数据，新起一行。如果小红可以到达目标位置，输出 ；否则，直接输出 。

示例1

输入

3
1 1 1 1 1 1
3 3 6 6 6 6
5 1 1 1 1 3

输出

YES
NO
YES

说明

对于第一组测试数据，其中一种可行的方案是，向上移动  步到达 ，然后向右移动  步到达 。
对于第二组测试数据，我们可以证明，小红无法通过给定的步数到达 。
对于第三组测试数据，其中一种可行的方案是，向右移动  步到达 、向左移动  步到达 、向右移动  步到达 、最后向上移动  步到达 。

算法知识视频讲解

Java

BraveCoder

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        
        while (T-- > 0) {
            long x = scanner.nextLong();
            long y = scanner.nextLong();
            long a = scanner.nextLong();
            long b = scanner.nextLong();
            long c = scanner.nextLong();
            long d = scanner.nextLong();
            
            // 计算y方向所需的最大公约数
            long gcdY = gcd(a, b);
            // 计算x方向所需的最大公约数
            long gcdX = gcd(c, d);
            
            // 判断y是否是gcd(a,b)的倍数，且x是否是gcd(c,d)的倍数
            if (y % gcdY == 0 && x % gcdX == 0) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
        
        scanner.close();
    }
    
    // 欧几里得算法计算最大公约数
    private static long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

发表于 2025-09-07 16:54:14 回复(0)

Java

牛客281381469号

看懂规律后实际上是比较简单的题，求最大公约数gcd的题，
我们可以无数次根据规定步数向上下左右走，竖直方向所能到达的地方是单次往上下方向走的最大公约数的倍数，
左右方向所能到达的地方是左右的最大公约数的倍数。
比如3和5，最大公约数是1，任何方向都能到达。2和8，最大公约数是2，任何2的倍数位置都能到达，比如-4 -2 0 2 4.
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int T = in.nextInt();
            for (int i = 0; i < T; i++) {
                int leftRight = in.nextInt();
                int upDown = in.nextInt();
                int up = in.nextInt();
                int down = in.nextInt();
                int left = in.nextInt();
                int right = in.nextInt();
                int shangXia = gcd(Math.abs(up), Math.abs(down));
                int zuoYou = gcd(Math.abs(left), Math.abs(right));
                if ((upDown % shangXia == 0) && (leftRight % zuoYou == 0)) {
                    System.out.println("YES");
                } else System.out.println("NO");
            }
        }
    }
    private static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
}

发表于 2025-07-26 01:00:35 回复(0)

Java

牛客430757235号

//只要分析得出来输出yes和no需要满足条件就很容易输出YES需要满足 x % （c,d的公共公因数）== 0 且 y % （a,b的公共公因数）== 0 需要用到数学贝祖定理方法

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int T = in.nextInt();

in.nextLine();

while (T-- > 0) {

int x = in.nextInt();

int y = in.nextInt();

int a = in.nextInt();

int b = in.nextInt();

int c = in.nextInt();

int d = in.nextInt();

if (x % gcd(c, d) == 0 && y % gcd(a, b) == 0) {

System.out.println("YES");

} else {

System.out.println("NO");

}

private static int gcd(int a, int b) {

return b == 0 ? a : gcd(b, a % b);

}

发表于 2025-03-19 14:56:05 回复(0)

提交观点

问题信息

数论

难度：

3条回答 88收藏 217浏览

小红走网格

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题