Skip to content

11533: 【原1533】寻路

题目

题目描述

author: greatwall1995 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1533

Description

无头鬼Vagrant找不到路了!正直勇敢的DC乄mobula决定帮助她找到回家的路。

他们现在处在一个\(n*n\)的螺旋状网格图(如下图所示),Vagrant最初位于网格图的左上角(即图中S所处的位置),目标是要到达道路的尽头(图中T所在的位置)。

现在DC乄mobula已经带着Vagrant走到了位于第\(i\)行第\(j\)列的格子,请你告诉他目前走了多少步。

Input Format

共一行,包含三个整数\(n, x, y\),分别表示网格的规模,行号和列号。

Output Format

共一行,包含一个整数表示答案。

Sample Input 1

3 2 3

Sample Output 1

3

Sample Input 2

5 2 4

Sample Output 2

18

Limits

对于30%的数据,\(1≤n≤3\)

对于另外30%的数据,询问的格子位于网格的边界上

对于100%的数据,\(1≤n≤1000, 1≤x, y≤n\).

ligongzzz's solution

#include "iostream"
#include "algorithm"
using namespace std;

int main() {
    int n, x, y;
    cin >> n >> x >> y;
    //记录当前边数
    int gap = min(min(x - 1, n - x), min(y - 1, n - y));
    int num = n - 2 * gap;
    int step = n * n - num * num;

    int dx[] = { 0,1,0,-1 };
    int dy[] = { 1,0,-1,0 };
    //记录步数
    for (int status = 0, i = (n - num) / 2 + 1, j = i-1; i != x || j != y; step++) {
        i += dx[status];
        j += dy[status];
        //判断是否越界
        if (i + dx[status] > n - gap || i + dx[status]<gap + 1 || j + dy[status]>n - gap || j + dy[status] < gap + 1) {
            status = status < 3 ? status + 1 : 0;
        }
    }
    //输出
    cout << step-1;
    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

int main() {
    int **road, n, x = 1, y = 1, step = 0, turn = 0, x0, y0;
    cin >> n >> x0 >> y0;

    road = new int *[n + 2];

    for (int i = 0; i < n + 2; i++) {
        road[i] = new int[n + 2];
        for (int j = 0; j < n + 2; j++) {
            if (i == 0 || i == n + 1 || j == 0 || j == n + 1) {
                road[i][j] = -1;
            } else {
                road[i][j] = 0;
            }
        }
    }

    road[x0][y0] = 1;

    while (1) {
        if (road[x][y] == 1) {
            break;
        } else if (road[x][y] == -1) {
            if (turn == 0) {
                y--;
                turn = 1;
            } else if (turn == 1) {
                x--;
                turn = 2;
            } else if (turn == 2) {
                y++;
                turn = 3;
            } else if (turn == 3) {
                x++;
                turn = 0;
            }
            road[x][y] = -2;
        } else if (road[x][y] == 0 || road[x][y] == -2) {
            if (road[x][y] == 0) {
                step++;
            }
            road[x][y] = -1;
            if (turn == 0) {
                y++;
            } else if (turn == 1) {
                x++;
            } else if (turn == 2) {
                y--;
            } else if (turn == 3) {
                x--;
            }
        }
    }

    cout << step;

    for (int i = 0; i < n + 2; i++) {
        delete[] road[i];
    }
    delete[] road;

    return 0;
}

yyong119's solution

#include <cstdio>
using namespace std;

int steps(int n, int x, int y) {
    if (x == 1) return y;
    if (y == n) return x + n - 1;
    if (x == n) return 3 * n - y - 1;
    if (y == 1) return 4 * n - x - 2;
    return 4 * n - 4 + steps(n - 2, x - 1, y - 1);
}

int main() {

    int n, x, y;
    scanf("%d%d%d", &n, &x, &y);
    int ans = steps(n, x, y) - 1;
    printf("%d\n", ans);

    return 0;
}