Ngày 11-1-2019 - Bài 2

SPIRAL - Bảng xoắn ốc (ACMVN 10-2016 J)

Dữ liệu vào: standard input

Dữ liệu ra: standard output

Giới hạn thời gian: 3.0 giây

Giới hạn bộ nhớ: 128 megabyte

Đăng bởi: admin

Tùng có một bảng gồm N dòng N cột. Các dòng được đánh số từ 1 đến N từ trên xuống dưới, các cột được đánh số từ 1 đến N từ trái sang phải. Tùng điền bảng này với các con số từ 1 đến NxN theo hình xoắn ốc, bắt đầu từ ô (1, 1). Hình xoắn ốc đi từ ngoài vào trong theo chiều kim đồng hồ. Hình bên phải là ví dụ với bảng N = 5. Hiện tại, Tùng đang ở vị trí của ô số X và Tùng muốn chuyển đến ô của số Y bằng cách thực hiện một số bước di chuyển. Trong mỗi bước, Tùng chỉ có thể di chuyển từ ô số A đến ô số B nếu:

- A và B nguyên tố cùng nhau.
- Ô chứa số A và ô chứa số B có chung một cạnh.

Cho N, X, Y, Tùng muốn biết số bước di chuyển ít nhất để chuyển từ ô số X đến ô số Y.

Dữ liệu nhập:

- Dòng đầu tiên chứa số nguyên T là số lượng test. (1 ≤ T ≤ 10)

- Trong T dòng tiếp theo, mỗi test trên một dòng là 03 số nguyên N, X và Y (1 ≤ N ≤ 1.000, 1 ≤ X, Y ≤ N²).

Dữ liệu xuất:

- Với mỗi test, in ra số bước ít nhất để di chuyển từ ô số X đến ô số Y. Nếu không di chuyển được in ra -1

Ví dụ

• input
  1
  5 3 18
  output
  3

Thực hiện 3 bước:

- Từ ô số 3 chuyển qua ô số 4 (3 và 4 nguyên tố cùng nhau)
- Từ ô số 4 chuyển qua ô số 19 (4 và 19 nguyên tố cùng nhau)
- Từ ô số 19 chuyển qua ô số 18 (19 và 18 nguyên tố cùng nhau) 

Lời giải:

#include <bits/stdc++.h>

using namespace std;

int x,y,a[1007][1007],n,dx[4] = {1,-1,0,0},dy[4] = {0,0,-1,1},X1,Y1,X0,Y0,d[1007][1007],t;

int gcd(int a, int b)
{
    while (b > 0)
    {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

void taobang()
{
    int d2 = 1, c = n, id = 0;
    while (d2 < c)
    {
        for (int i = d2; i <= c; ++i) a[d2][i] = ++id;
        for (int i = d2 + 1; i <= c; ++i) a[i][c] = ++id;
        for (int i = c - 1; i >= d2; --i) a[c][i] = ++id;
        for (int i = c - 1; i > d2; --i) a[i][d2] = ++id;
        ++d2,--c;
    }
    if (n % 2) a[n / 2 + 1][n / 2 + 1] = n*n;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            if (a[i][j] == x) X0 = i, Y0 = j;
            if (a[i][j] == y) X1 = i, Y1 = j;
            d[i][j] = 0;
        }
}

void bfs()
{
    if (x == y)
    {
        cout << 0 << endl;
        return;
    }
    queue< pair<int,int> > Q;
    Q.push({X0,Y0});
    d[X0][Y0] = 1;
    while (!Q.empty())
    {
        int u = Q.front().first, v = Q.front().second;
        Q.pop();
        for (int i = 0; i < 4; ++i)
        {
            int xx = u + dx[i], yy = v + dy[i];
            if (xx == 0 || yy == 0 || xx > n || yy > n) continue;
            if (d[xx][yy]) continue;
            if (gcd(a[u][v],a[xx][yy]) > 1) continue;
            if (xx == X1 && yy == Y1)
            {
                cout << d[u][v] << endl;
                return;
            }
            d[xx][yy] = d[u][v] + 1;
            Q.push({xx,yy});
        }
    }
    cout << -1 << endl;
}

void nhap()
{
    //freopen("test.txt","r",stdin);
    ios_base::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    cin >> t;
    while (t--)
    {
        cin >> n >> x >> y;
        taobang();
        bfs();
    }
}

int main()
{
    nhap();
    return 0;
}