首页 > 试题广场 >

小红走网格

[编程题]小红走网格

热度指数：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

说明

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

算法知识视频讲解

Python3

emdnauoy

n = input()

def is_t(a, b, x):

for i in range(10):

for j in range(10):

res = i * a + j * b

if res == x:

return True

return False

while True:

try:

x,y,a,b,c,d = map(int,input().split())

b = -b

c = -c

if is_t(a,b,x) and is_t(c,d,y):

print('YES')

else:

print('NO')

except:

break

不够完善

发表于 2025-04-20 13:36:42 回复(2)

Python3

实习_机器学习_广东或四川_5月中可入职

最多只能走到a,b的最大公约数的倍数，原先手搓的暴力算gcd超时了，换成了辗转相除法

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def solve():
    x, y, a, b, c, d = map(int, input().split())
    g_x = gcd(c, d)  # 最多只能走到c, d最大公约数的倍数
    g_y = gcd(a, b)

    if x % g_x == 0 and y % g_y == 0:
        print("YES")
    else:
        print("NO")

T = int(input())
for _ in range(T):
    solve()

发表于 2025-03-26 14:08:47 回复(0)

提交观点

问题信息

数论

难度：

4条回答 88收藏 218浏览

小红走网格

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题