c 언어:금화 배열 의 문제
4522 단어 금화 어 레이
금화 진열 게임 의 규칙 은 다음 과 같다.(1)매번 한 줄 의 금 화 를 뒤 집어 원래 의 위치 에 놓 을 수 있다.
(2)매번 2 열 을 선택 하여 이 2 열 금화 의 위 치 를 교환 할 수 있 습 니 다.
프로 그래 밍 작업:금화 배열 의 초기 상태 와 목표 상 태 를 정 하고 금화 게임 규칙 에 따라 금화 배열 을 초기 상태 에서 목표 상태 로 바 꾸 는 데 필요 한 최소 변환 횟수 를 계산 합 니 다.
Input
입력 데이터 가 여러 그룹의 데이터 가 있 습 니 다.첫 번 째 줄 에는 1 개의 정수 k 가 있 는데 k 조 데이터 가 있 음 을 나타 낸다.각 그룹의 데이터 의 첫 줄 에는 두 개의 정수 m 와 n 이 있다.아래 의 m 줄 은 금화 배열 의 초기 상태 로 줄 마다 n 개의 숫자 가 이 줄 의 금화 상 태 를 나타 내 고 0 은 금화 의 정면 이 위로 향 하고 1 은 뒷면 이 위로 향 하 는 것 을 나타 낸다.이 어 m 줄 은 금화 배열 의 목표 상태 입 니 다.
Output
계 산 된 최소 변환 횟수 를 입력 데이터 의 순서에 따라 출력 합 니 다.해당 데이터 가 풀 리 지 않 을 때 출력-1.
코드 는 다른 사람의 것 이 라 잘 쓴 것 같 습 니 다.이 블 로 그 를 쓰 는 것 은 주로 생각 을 되새 기 려 는 것 이다.
매 거 1~m 중 매 열 이 1 열 인 경우,
//1~n 줄 에서 만족 하지 않 는 줄 을 찾 아 줄 변환
//매 거 진 이 열 이 규칙 에 따라 목표 행렬 로 성공 적 으로 전환 된다 면 이때 행렬 과 원 행렬 의 차 이 는 열 순서 에 만 있 을 것 입 니 다.
이때 i=2 열(2 열)부터 목표 행렬 의 i 열 과 비교 하여
다 르 면 이 행렬 의 j 열(즉=i+1~m)이 목표 행렬 의 i 열 과 같은 것 이 있 는 지,있 으 면 이 행렬 의 j 열!=목표 매트릭스 제 j 열,1 차 열 변환
//조건 에 맞 는 열 을 찾 지 못 하면 매 거 진 이 열 은 첫 번 째 열 로 주어진 규칙 에 따라 목표 행렬 로 바 꿀 수 없습니다.
#include<stdio.h>
const int inf = 99999;
const int N = 101;
int a[N][N],b[N][N],temp[N][N]; //a ,b
int n,m;
int need;//
void ChangeL(int x,int y)//
{
if(x==y)return;
int i;
for(i=1;i<=n;i++)
{
int tt=temp[i][y];
temp[i][y]=temp[i][x];
temp[i][x]=tt;
}
need++;
}
void ChangeH(int x)//
{
int i;
for(i=1;i<=m;i++)
{
temp[x][i]^=1;
}
}
bool Same(int x,int y) //
{
int i;
for(i=1;i<=n;i++)
if(b[i][x]!=temp[i][y])return false;
return true;
}
int main()
{
int tests;
scanf("%d",&tests); //
while(tests--)
{
scanf("%d%d",&n,&m); //n ,m
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&b[i][j]);
int k;
int ans=inf; //ans ,
for(k=1;k<=m;k++)//
{
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
temp[i][j]=a[i][j];
need=0;
ChangeL(1,k);
// ,
for(i=1;i<=n;i++)
{
if(temp[i][1]!=b[i][1])//
{
ChangeH(i);//
need++;
}
}
bool find;
for(i=1;i<=m;i++)//
{
find=false;
if(Same(i,i))
{
find=true;
continue;
}
for(j=i+1;j<=m;j++)// temp b i
{
if(Same(i,j))//temp j b i
{
if(Same(j,j))continue;//temp j b j
ChangeL(i,j);// temp i,j
find=true;
break;
}
}
if(find==false)//
{
break;
}
}
if(find==true&&need<ans)
ans=need;
}
if(ans<inf)
printf("%d
",ans);
else
printf("-1
");
}
return 0;
}