Ring

Ring

时间限制: 1 Sec  内存限制: 128 MB

题目描述

一个n×n的矩阵，可以分成一些环(如图a中，n=5，可以划分成3个环)，每个环上的数字都可以沿着环顺时针或者逆时针转动，每次转动只能将任意一个环顺时针或者逆时针转动一格。初始状态如图a，将矩阵从左到右、从上到下依次用1到n×n填满。现在给你一个局面，请问至少通过多少次环的转动能使矩阵恢复到初始状态？
例如，图b的局面可以通过，最外圈逆时针转动两格，第二圈顺时针转动一格，恢复到初始状态(图a)，即至少转动三次。

输入

第一行输入一个正整数n。接下来n行，每行输入n个用空格隔开的正整数，第i行第j个数aij(aij≤1,000)，表示给定的n×n的矩阵局面。

输出

若给定的矩阵局面可以通过环的转动回到初始状态，则输出两行，第一行为“YES”(输出不包含引号)，第二行为一个非负整数，表示至少需要转动几次；否则，输出“NO”(输出不包含引号)。

样例输入

复制样例数据

5
11 6 1 2 3
16 8 9 14 4
21 7 13 19 5
22 12 17 18 10
23 24 25 20 15

样例输出

YES
3

提示

对于 40% 的数据，满足n≤4，且给定局面中1到n×n的数字都出现且仅出现一次。
对于 80% 的数据，满足n≤6，且给定局面中1到n×n的数字都出现且仅出现一次。
对于 100% 的数据，满足n≤6。

先将一个个环全部拆下来放到数组中，然后将初始状态的和现在的状态比较，是否可以到达。

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n;
int a[7][7], b[7][7];
int p[5][40], now[5][40], ans; //now记录的现在的各个环,p记录的初始的各个环


bool dfs(int x){
	if(x == (n + 1) / 2 + 1) return true;
	int cnt = 1, f = 0, t = 1, num = 0;
	while(now[x][t] != p[x][1] && t <= now[x][0]) t++, num++;
	while(cnt <= p[x][0]){
		if(now[x][t] != p[x][cnt]){
			f = 1;
			break;
		}else{
			if(t == now[x][0]) t = t - now[x][0] + 1;//注意是个环
			else t++;
			cnt++;
		}
	}
	ans += min(num, now[x][0] - num);//因为可以是逆时针，所以要取最小值
	if(!f) return dfs(x + 1);
	else return false;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			scanf("%d", &a[i][j]);
		}
	}
	int cnt = 1;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			b[i][j] = cnt++;
		}
	}
	int t = (n - 1) * 4;//每一个环的数字的个数
	for (int i = 1; i <= (n + 1) / 2; i++){
		int x = i, y = i;
		cnt = 1;
		if((n & 1) && !t) t = 1;//奇数的时候，当中有一块
		now[i][0] = t;
		int f = 1, tt = t / 4;
		while(cnt <= t){
			now[i][cnt++] = a[x][y];
			if(f == 1){
				y++;
				if(y == i + tt) f = 2;
			}else if(f == 2){
				x++;
				if(x == i + tt) f = 3;
			}else if(f == 3){
				y--;
				if(y == i) f = 4;
			}else x--;
		}
		t -= 8;
	}
	t = (n - 1) * 4;
	for (int i = 1; i <= (n + 1) / 2; i++){
		int x = i, y = i;
		cnt = 1;
		if((n & 1) && !t) t = 1;
		p[i][0] = t;
		int f = 1, tt = t / 4;
		while(cnt <= t){
			p[i][cnt++] = b[x][y];
			if(f == 1){
				y++;
				if(y == i + tt) f = 2;
			}else if(f == 2){
				x++;
				if(x == i + tt) f = 3;
			}else if(f == 3){
				y--;
				if(y == i) f = 4;
			}else x--;
		}
		t -= 8;
	}
	if(dfs(1)) printf("YES\n%d\n", ans);
	else printf("NO\n");

	return 0;
}
/**/