首页 > 试题广场 >

小红走网格

[编程题]小红走网格
  • 热度指数:3399 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 1024M,其他语言2048M
  • 算法知识视频讲解
\hspace{15pt}在二维平面坐标系中,小红初始位置为 (0, 0)。她可以向四个方向移动,移动的步数由四个正整数 abcd 定义,分别表示小红向上、向下、向左和向右移动一次的步数。
\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)。请判断小红是否可以通过上述步数到达目标位置。

输入描述:
\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 10^4\right) 代表数据组数,每组测试数据描述如下:
\hspace{15pt}在一行上输入六个整数 x, y, a, b, c, d \left(1 \leqq x, y, a, b, c, d \leqq 10^9 \right) 代表目标位置所在坐标、向上下左右四个方向单次移动的步数。


输出描述:
\hspace{15pt}对于每一组测试数据,新起一行。如果小红可以到达目标位置,输出 \rm YES;否则,直接输出 \rm NO
示例1

输入

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

输出

YES
NO
YES

说明

\hspace{15pt}对于第一组测试数据,其中一种可行的方案是,向上移动 1 步到达 (0, 1),然后向右移动 1 步到达 (1, 1)
\hspace{15pt}对于第二组测试数据,我们可以证明,小红无法通过给定的步数到达 (3, 3)
\hspace{15pt}对于第三组测试数据,其中一种可行的方案是,向右移动 3 步到达 (3, 0)、向左移动 1 步到达 (2, 0)、向右移动 3 步到达 (5, 0)、最后向上移动 1 步到达 (5, 1)
package main

import (
	"fmt"
)

func main() {
	var T int
	fmt.Scan(&T)
	results := make([]string, T)

	for i := 0; i < T; i++ {
		nums := make([]int, 6)
		for j := 0; j < 6; j++ {
			fmt.Scan(&nums[j])
		}
		x := nums[0]
		y := nums[1]
        g_x := gcd(nums[4], nums[5])
        g_y := gcd(nums[2], nums[3])
        
        if x%g_x == 0 && y%g_y == 0 {
            results[i] = "YES"  
        } else {
            results[i] = "NO"
        }
	}

	for _, v := range results {
		fmt.Println(v)
	}
}

func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

发表于 2025-05-19 14:09:53 回复(0)