首页 > ACM题库 > HDU-杭电 > HDU 4708-Rotation Lock Puzzle-计算几何-[解题报告]HOJ
2015
09-17

HDU 4708-Rotation Lock Puzzle-计算几何-[解题报告]HOJ

Rotation Lock Puzzle

问题描述 :

Alice was felling into a cave. She found a strange door with a number square matrix. These numbers can be rotated around the center clockwise or counterclockwise. A fairy came and told her how to solve this puzzle lock: “When the sum of main diagonal and anti-diagonal is maximum, the door is open.”.
Here, main diagonal is the diagonal runs from the top left corner to the bottom right corner, and anti-diagonal runs from the top right to the bottom left corner. The size of square matrix is always odd.

Pet

This sample is a square matrix with 5*5. The numbers with vertical shadow can be rotated around center ‘3’, the numbers with horizontal shadow is another queue. Alice found that if she rotated vertical shadow number with one step, the sum of two diagonals is maximum value of 72 (the center number is counted only once).

输入:

Multi cases is included in the input file. The first line of each case is the size of matrix n, n is a odd number and 3<=n<=9.There are n lines followed, each line contain n integers. It is end of input when n is 0 .

输出:

Multi cases is included in the input file. The first line of each case is the size of matrix n, n is a odd number and 3<=n<=9.There are n lines followed, each line contain n integers. It is end of input when n is 0 .

样例输入:

5
9 3 2 5 9
7 4 7 5 4
6 9 3 9 3
5 2 8 7 2
9 9 4 1 9
0

样例输出:

72 1

题意:给出一个n*n的矩阵,旋转每一圈数字,求出对角线可能的最大值,以及转到最大时的最小距离。

只要分析每一层就可以了,本来想用地址传递二维数组,发现行不通,改了一下就行了。

这里有个坑,比如:

1 1 9 9 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

很明显最大的就是将一个9转到矩阵角,而这里更新最大值时很容易把另一种情况屏蔽掉,从而错过了更少步骤达到最大值的方法。

代码:

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        3.cpp
*  Create Date: 2013-09-08 14:21:58
*  Descripton:  simulate 
*/

#include <cstdio>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)

const int MAXN = 100;
int a[MAXN][MAXN];
int n, sum, cnt;

void solve(int k, int l) {
	int tmp = -0xffffff, tt = 0;
	rep(i, l - 1) {
		int t = a[k][k + i] + a[k + i][k + l - 1] + a[k + l - i - 1][k + 0] + a[k + l - 1][k + l - i - 1];
		if (tmp <= t) {
			if (tmp == t)
				tt = min(tt, min(i, l - i - 1));
			else
				tt = min(i, l - i - 1);
			tmp = t;
		}
	}
	sum += tmp;
	cnt += tt;
}

int main() {
	while (scanf("%d", &n) && n) {
		rep(i, n) rep(j, n)
			scanf("%d", &a[i][j]);
		int l = n / 2;
		sum = a[l][l];
		cnt = 0;
		rep(i, l)
			solve(i, n - 2 * i);
		printf("%d %d\n", sum, cnt);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/hcbbt/article/details/11401809