牛吃草问题，奶牛的牧场分成了一个n行n列的矩阵

牛吃草问题
描述

一天奶牛cow做了一个梦，来到了一个神奇的牧场，这片牧场被分成了一个n行n列的矩阵，每个格子里的草在cow吃完离开这个格子后会马上长出来，所以这里的草怎么也吃不完，cow可开心了，cow沿着整个矩阵开始不停的吃草，第一行吃完，马上在第二行开头吃依次往复，如果他吃到最后一行最后一列，就会马上回到第一行第一列，继续刚刚的过程，现在已知COW吃完一个格子的草需要1小时，问t小时后，cow在哪。

day13-02.zip

输入
第一行一个整数T(T<=100000)，表示数据组数
每组数据一行，两个整数，n,t分别表示矩阵大小和时间（n<=10,t<=500000）

输出
一行，两个整数，分别是行和列，表示cow的位置，用空格隔开

输入样例 1

1
4 2
输出样例 1

1 3

#include<iostream>
using namespace std;

int main()
{
    int T, n, t;
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        cin >> n >> t;
        t = t % (n*n);
        int row = t / n + 1;
        int col = t % n + 1;
        cout << row << " " << col << endl;
    }
    return 0;
}

#include <iostream>
using namespace std;
int main(){
    int t=2;//时间
    int n=4;//方格行列大小 
    int row=t/n+1;
    int col=t%n+1;
     printf("%d   %d",row,col);
    return 0;
} 

【以下回答由 GPT 生成】

分析

根据问题描述，当牛吃到最后一行最后一列时，会回到第一行第一列。这说明在一个周期内，牛吃草的位置是有规律可循的。我们可以通过分析规律，找到牛在给定时间后的位置。

解决方案

1. 首先，我们需要确定牛在一个周期内吃草的路径。观察示例题中的矩阵，我们可以发现以下规律：
   • 当矩阵的行数和列数都是奇数时，牛吃草的路径是一个“Z”字型路线。即从第一行第一列开始向右上方走，走到最后一行后折返，然后再次向右上方走，如此往复。
   • 当矩阵的行数和列数都是偶数时，牛吃草的路径是一个“S”字型路线。即从第一行第一列开始向右上方走，走到最后一行后折返，然后再次向右上方走，如此往复。
   • 当矩阵的行数和列数中有一个是奇数，另一个是偶数时，牛吃草的路径是一个“V”字型路线。即从第一行第一列开始向右上方走，走到最后一列后折返，然后再次向右上方走，如此往复。
2. 确定了牛在一个周期内吃草的路径后，我们还需要计算在给定时间内，牛走过了多少个完整的路径。
   • 如果给定时间t小于等于一个周期的时间(length)，则牛的位置就是路径上的第t个位置。
   • 如果给定时间t大于一个周期的时间(length)，则牛的位置的行数就是牛在一个周期内路径上的第t%length个位置的行数，列数就是牛在一个周期内路径上的第t%length个位置的列数。
3. 基于以上思路，我们可以编写代码实现。

代码实现

def find_bull_position(n, t):
    # 确定周期内吃草的路径
    if n % 2 == 0:  # 偶数行数和列数
        max_row = min(n, t // 2) + 1  # 计算牛在一个周期内行数的最大值
        max_col = (t % 2) * n + 1  # 计算牛在一个周期内列数的最大值
    else:  # 奇数行数和列数
        max_row = min(n, t // 2 + 1) + 1
        max_col = (t % 2) * (n - 1) + 1

    # 计算牛在给定时间内走过的完整路径的个数
    length = 2 * n - 2 if n % 2 == 0 else 4 * n - 4
    cycle_cnt = t // length  # 完整路径的个数

    # 计算牛在给定时间内的位置
    row = (cycle_cnt * max_row) % n if n % 2 == 0 else (cycle_cnt * max_row - 1) % n
    col = (cycle_cnt * max_col) % n if n % 2 == 0 else (cycle_cnt * max_col - 1) % n

    return row, col

# 测试
test_input = [
    (4, 2),
    (5, 10),
    (6, 5)
]

for n, t in test_input:
    row, col = find_bull_position(n, t)
    print(f"牛在 {t} 小时后的位置是：{row} {col}")

复杂度分析

• 时间复杂度：O(1)
• 空间复杂度：O(1)