好贷网好贷款

hdu 4708 Rotation Lock Puzzle(模拟)

发布时间:2016-12-4 16:26:17 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 4708 Rotation Lock Puzzle(模拟)",主要涉及到hdu 4708 Rotation Lock Puzzle(模拟)方面的内容,对于hdu 4708 Rotation Lock Puzzle(模拟)感兴趣的同学可以参考一下。

题目连接:4708 Rotation Lock Puzzle 题目大意:现在给出一个n * n 的矩阵, 像题目中图所给的一样,矩阵可以分成n / 2个圈, 每个圈可以进行顺时针可逆时针的旋转, 现在要求在矩阵的两条对角之和要最大并且旋转次数最少, 输出最大值和最少步数。 解题思路:先把每一个圈复制到数组中处理, 求的每个圈的最大值, 以及到达最大值的最短路径,求最短路径的时候要注意圆圈可以逆时针并且顺时针旋转。 #include <stdio.h> #include <string.h> const int N = 105; int min(int a, int b) { return a > b ? b : a; } int n, sum, cnt, tmp[N][N * N], g[N][N], son[N]; void read() { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &g[i][j]); } void hand(int k) { for (int i = k; i < n - k; i++) tmp[k][son[k]++] = g[k][i]; for (int i = k + 1; i < n - k - 1; i++) tmp[k][son[k]++] = g[i][n - k - 1]; for (int i = n - k - 1; i >= k; i--) tmp[k][son[k]++] = g[n - k - 1][i]; for (int i = n - k - 2; i >= k + 1; i--) tmp[k][son[k]++] = g[i][k]; } void solve(int k) { int Max = 0, id = 0, dist = n - 2 * k - 1; int t = n - k - 1; for (int i = 0; i < t; i++) { int a = 0; for (int j = 0; j < 4; j++) a += tmp[k][i + j * dist]; if (a > Max) { Max = a; id = min(i, t - i); } else if (a == Max) { if (min(i, t - i) < id) id = min(i, t - i); } } sum += Max; cnt += id; } int main() { while(scanf("%d", &n) == 1 && n) { memset(tmp, 0, sizeof(tmp)); memset(son, 0, sizeof(son)); memset(g, 0, sizeof(g)); sum = cnt = 0; read(); for (int i = 0; i < n / 2; i++) hand(i); for (int i = 0; i < n / 2; i++) solve(i); printf("%d %d\n", sum + g[n / 2][n / 2], cnt); } return 0; }

上一篇:项目报错四
下一篇:PMBOK学习笔记-项目管理、项目集管理和项目组合管理间的关系

相关文章

相关评论