原理

问题目标：模拟华小科按照给定的转移规则在二维网格中移动的路径，直到无法继续移动为止。

• 每个位置 (Tx, Ty) 对应一个转移规则，存储在二维数组 travel 中。
• travel[Tx][2*Ty-1] 表示下一个位置的横坐标，travel[Tx][2*Ty] 表示纵坐标。
• 当转移坐标为 (0, 0) 时，停止移动。

步骤

1. ​输入初始化：
   • 读取网格参数 m（列数）、n（行数），以及初始位置 (Sx, Sy)。
   • 初始化一个 (n+1) x (2m+1) 的二维数组 travel，存储转移规则。
2. ​填充转移规则：
   • 按行读取转移规则，每行有 2m 个整数，表示每个位置的转移坐标。
3. ​模拟移动：
   • 从初始位置 (Sx, Sy) 开始，输出当前位置。
   • 根据当前坐标查询 travel 数组，计算下一个坐标。
   • 若下一个坐标为 (0, 0)，停止；否则更新当前位置并重复。

图示法表示步骤（示例：m=1, n=2, Sx=1, Sy=1）

1. ​输入转移规则：

   travel[1][1] = 2, travel[1][2] = 1  
   travel[2][1] = 0, travel[2][2] = 0  

2. ​模拟过程：
   • 初始位置 (1, 1)，输出 1 1。
   • 查表得下一位置为 (2, 1)，输出 2 1。
   • 查表得下一位置为 (0, 0)，停止。

代码关键行注释

vector<vector<int>> travel(n+1, vector<int>(2*m+1, 0));  
// 初始化 (n+1) 行、(2m+1) 列的二维数组，默认值 0  

for (int i = 1; i <= n; i++) {  
    for (int j = 1; j <= 2*m; j++) {  
        cin >> travel[i][j];  
    }  
}  
// 读取转移规则，填充 travel 数组的第 1~n 行  

int nextx = travel[Tx][2*Ty - 1];  
int nexty = travel[Tx][2*Ty];  
// 根据当前坐标 (Tx, Ty)，计算下一个坐标  

if (nextx == 0 && nexty == 0) break;  
// 终止条件：下一坐标为 (0, 0)  

完整代码程序

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int m,n,Sx,Sy;
    cin>>m>>n>>Sx>>Sy;
    vector<vector<int>> travel(n+1,vector<int>(2*m+1,0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=2*m;j++){
            cin>>travel[i][j];
        }
    }
    int Tx=Sx,Ty=Sy;
    cout<<Tx<<" "<<Ty<<endl;

    while(1){
        int nextx=travel[Tx][2*Ty-1];
        int nexty=travel[Tx][2*Ty];
        if(nextx==0&&nexty==0) break;
        Tx=nextx;
        Ty=nexty;
        cout<<Tx<<" "<<Ty<<endl;
    }
    return 0;
}

时间复杂度

• ​时间复杂度：O(K)，其中 K 是移动路径的长度。每次移动只需查表操作，时间复杂度为 O(1)。
• ​空间复杂度：O(n*m)，用于存储 travel 数组。

总结

1. ​代码特点：
   • 直接根据转移规则模拟路径，逻辑简单。
   • 通过二维数组快速查询下一步坐标。
2. ​潜在问题：
   • ​数组越界：若转移后的坐标 nextx 或 nexty 超出有效范围（如 nextx > n 或 nexty > m），会导致访问越界。
   • ​未初始化区域：travel 数组的第 0 行和第 0 列未填充数据，可能被错误访问。
3. ​适用场景：
   • 题目保证转移路径最终指向 (0, 0)，且不会越界。
   • 若数据存在循环或无效坐标，代码可能无法终止或崩溃。