oj.uz

답안 #92653

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
92653 2019-01-04T09:33:29 Z SamAnd Riddick's Cube (IZhO13_riddicks) C++17
100 / 100
 6 ms 504 KB 
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N=7,INF=100500;

int ans=INF;
int a[N][N];
int b[N][N];
int c[N][N];
int n,m;
int t[N],s[N];
bool stg()
{
	bool z=true,z1=true;
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<m;++j)
		{
			if(c[i][j]!=c[i][0])
				z=false;
		}
	}
	for(int j=0;j<m;++j)
	{
		for(int i=0;i<n;++i)
		{
			if(c[i][j]!=c[0][j])
				z1=false;
		}
	}
	return (z||z1);
}
void ab()
{
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<m;++j)
		{
			b[(i+s[j])%n][j]=a[i][j];
		}
	}
}
void bc()
{
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<m;++j)
		{
			c[i][(j+t[i])%m]=b[i][j];
		}
	}
}
void ubd()
{
	ab();
	bc();
	if(stg())
	{
		int yans=0;
		for(int i=0;i<n;++i)
		{
			yans+=min(t[i],m-t[i]);
		}
		for(int i=0;i<m;++i)
		{
			yans+=min(s[i],n-s[i]);
		}
		ans=min(ans,yans);
	}
}
bool stg1(int x,int r)
{
	int q[N],p[N];
	for(int i=0;i<m;++i)
	{
		q[(i+t[0])%m]=b[0][i];
		p[(i+r)%m]=b[x][i];
	}
	for(int i=0;i<m;++i)
		if(p[i]!=q[i])
			return false;
	return true;
}
void rec(int x,int y)
{
	if(x==n && y==m)
	{
		ubd();
		return;
	}
	if(y!=m)
	{
		for(int i=0;i<n;++i)
		{
			s[y]=i;
			rec(x,y+1);
		}
	}
	else
	{
		if(x==0)
		{
			ab();
			for(int i=0;i<m;++i)
			{
				t[x]=i;
				rec(x+1,y);
			}
		}
		else
		{
			int z=INF,zi;
			for(int i=0;i<m;++i)
			{
				if(stg1(x,i) && min(i,m-i)<z)
				{
					zi=i;
					z=min(i,m-i);
				}
			}
			if(z==INF)
				return;
			t[x]=zi;
			rec(x+1,y);
		}
	}
}
int main()
{
	//freopen("riddicks.in","r",stdin);
	//freopen("riddicks.out","w",stdout);
	///in
	cin>>n>>m;
	for(int i=0;i<n;++i)
		for(int j=0;j<m;++j)
			cin>>a[i][j];
	/////
	rec(0,0);
	//out
	cout<<ans<<endl;
//	system("pause");
	return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 3 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 6 ms 504 KB Output is correct
15 Correct 5 ms 256 KB Output is correct
16 Correct 5 ms 256 KB Output is correct
17 Correct 5 ms 256 KB Output is correct
18 Correct 5 ms 256 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct