c 언어:금화 배열 의 문제

4522 단어 금화 어 레이
m*n(m<=100,n<=100)개의 금화 가 데스크 톱 에 m 줄 n 열 로 늘 어선 금화 배열 이 있 습 니 다.모든 금화 나 정면 이 위로 향 하거나 뒷면 이 위로 향 합 니 다.숫자 로 금화 상 태 를 표시 하고 0 은 금화 의 정면 이 위로 향 하고 1 은 뒷면 이 위로 향 하 는 것 을 나타 낸다.
금화 진열 게임 의 규칙 은 다음 과 같다.(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;
 }

좋은 웹페이지 즐겨찾기