洛谷P2239题解

洛谷P2239题解

题目信息：

题目传送门：https://www.luogu.com.cn/problem/P2239
题目知识点：模拟，数学

分析1

第一个思路是绘图，从起点开始运动，每次运动到越界或者有赋过值的点就改变方向，这样的好处是不用考虑点具体的运动规律，但是很不幸maxn高达30000，如果真的用了这个方法只能和蒟蒻一样喜提MLE

参考代码

---

#include<cstdio>
const int maxn = 20005;
const int dx[4] = { 0,1,0,-1 };
const int dy[4] = { 1,0,-1,0 };int buf[maxn][maxn];
int n, i, j, flag;int main() {scanf("%d%d%d", &n, &i, &j);int v = 1;int x = 1, y = 1;for (int i = 1; i <= n * n; i++) {buf[x][y] = v++;x += dx[flag];y += dy[flag];if (x<1 || x>n || y<1 || y>n || buf[x][y]) {x -= dx[flag];y -= dy[flag];flag = (flag + 1) % 4;x += dx[flag];y += dy[flag];}}printf("%d\n", buf[i][j]);return 0;
}

分析2

想要找到i,j位置没有必要开一个表，分析运动路径即可
以n == 4为例子运动的长度为3 3 3 2 2 1 1，归纳发现除了第一次剩下的每有两次运动长度-1，而每次运动到头改变方向，由此可以写出代码

代码

#include<cstdio>
#define ll long long
int n, r ,c;
const int dx[4] = { 0,1,0,-1 };
const int dy[4] = { 1,0,-1,0 };
int x = 1, y = 1, dire;
ll v = 1;int main() {scanf("%d%d%d", &n, &r, &c);for (int i = 1; i < n; i++) {x += dx[dire];y += dy[dire];v++;if (x == r && y == c) {printf("%d\n", v);return 0;}}dire = 1;int t = n-1,cnt = 0,round=0;while (x!=r||y!=c) {x += dx[dire];y += dy[dire];cnt++; v++;if (cnt == t) {dire = (dire + 1) % 4;round++;if (round % 2 == 0)t--;cnt = 0;}}printf("%lld\n", v);return 0;
}

最后