时间戳

首页 > 解决方案 > 这段代码背后的逻辑和方法是什么？

c++ - 这段代码背后的逻辑和方法是什么？

问题描述

您必须访问所有单元格是 n*m 网格，您只能访问每个单元格一次并且您必须访问它们的方式是，当从一个单元格移动到另一个单元格时，向量（从数学上讲）（即ordered_pa​​ir (dx,dy)) 不再用于任何其他移动。也可能有其他解决方案，但我对为什么这个解决方案有效特别感兴趣。这个问题来自codeforces https://codeforces.com/contest/1180/problem/D

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n,m;
    cin>>n>>m;
    int st=0,end=n*m-1;
    for(int i=0;i<n*m;i++) {
        if(i%2==0) {
             cout<<st/m+1<<' '<<st%m+1<<endl;
             st++;
        }
        else {
            cout<<end/m+1<<' '<<end%m+1<<endl;
            end--;
        }
    }
}

标签： c++algorithm

解决方案

该算法以网格的某种顺序在第一个和最后一个尚未输入的单元格之间循环。我们需要 2 件来说明它的工作原理：

首先，我们注意到，对于排序这样一个网格（行或列主要）的典型方法，任何向量都由其在排序中的步长唯一标识（主要和次要部分实际上是除数和余数）各自边的长度，这两个部分是相互独立的）。

其次，我们的排序步骤的长度是单调递减的，因为我们减少了它可以移动每一步的可能排序值的数量，因为我们删除了它可能到达的最远点。

当我们把它结合起来时，我们得到所有的移动必须是不同的，因为每个移动在顺序上都有不同的长度，不同长度的步有唯一的向量移动。

请注意，由于在移动上也有一个符号，这也构成了一个不同的向量，并且我们已经采用了所有的排序长度，所以我们已经用完了所有可能的移动向量的一半（另一半是反向运动），我们可以由此证明所有满足问题的移动集也必须具有这个属性。

推荐阅读