1433.数码问题

Time Limits: 1000 ms Memory Limits: 65536 KB

Description

Alice有一个N*N的格子，把1-N^2按照从上到下从左到右的顺序填进表格中，允许在表格上进行两种操作：
　　(1) 旋转行——这一行的数向右移动一个位置，而最后一列的数会移到第一列；
　　(2) 旋转列——这一列的数向下移动一个位置，最后一行的数会移到第一行。
　　Alice想把数X移到（R,C）处可以采用以下方法：
　　•如果X不在C这一列，通过旋转行操作把X移到C这一列；
　　•如果X不在R这一行，通过旋转列操作把X移到R这一行。
　　下面是一个把6移到（3，4）的例子：
　　
　　Alice现在想采用上述方法，依次把K个数移到各自的目标位置，编程计算每个数需要几次操作。

Input

第一行包含两个整数N(12<=N<=10000)和K(1<=K<=1000)。
　　接下来K行，每行包含三个整数X(1<=X<=N^2)、R和C(1<=R,C<=N)，描述需要移动的数以及目标位置。
　　Alice必须按照输入顺序依次移动。

Output

输出K行，每行输出一个整数，表示操作次数。

Sample Input

输入1：
4 1
6 3 4

输入2：
4 2
6 3 4
6 2 2

输入3：
5 3
1 2 2
2 2 2
12 5 5

Sample Output

输出1：
3

输出2：
3
5

输出3：
2
5
3

Code

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4+5;
const int MAXK = 1e3+5;
struct Node {
    int val, fx, fy;
    int x, y;
}a[MAXK];
int n, k;
int main() {
    cin>>n>>k;
    for (int i=1; i<=k; i++) {
        cin>>a[i].val>>a[i].fx>>a[i].fy;
        --a[i].fx;
        --a[i].fy;
        --a[i].val;
        a[i].x=a[i].val / n;
        a[i].y=a[i].val % n;
    }
    for (int i=1; i<=k; i++) {
        a[i].fx += (a[i].x > a[i].fx ? n : 0);
        a[i].fy += (a[i].y > a[i].fy ? n : 0);
        int tempx=a[i].fx - a[i].x;
        int tempy=a[i].fy - a[i].y;
        cout<<tempx+tempy<<endl;
        for (int j=i; j<=k; j++) {
            if (a[j].x == a[i].x) {
                a[j].y = ( a[j].y + tempy ) % n;
            }
        }
        for (int j=i+1; j<=k; j++) {
            if (a[j].y == a[i].y) {
                a[j].x = ( a[j].x + tempx ) % n;
            }
        }
    }
    return 0;
}