Codeforces Round #806 (Div. 4) - E

문제 출처:

https://codeforces.com/contest/1703/problem/E

 

문제 분석:

들어온 도형을 90, 180, 270 돌린 모든 도형이 동일해 지도록 각 타일을

0-> 1, 1-> 0으로 바꾸는 문제이다.

 

문제 해결:

각 도형의 좌표가 (x,y)라면 90도 돌렸을 때 이 좌표는 (y, n-1-x)가 된다는 점을 이용하여

이를 각각 90도씩 4번 돌리면서 해당 좌표에 1이 많은지 0이 많은지를 체크한후

더 적은 값 만큼 바꿔주면 되는 문제이다.

 

내 소스코드:

// freopen("input.txt", "r", stdin);
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <cstring>
#include <list>
#include <set>
#include <string.h>
#include <map>
#include <limits.h>
#include <stdlib.h>
#include <typeinfo>
#include <bitset>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int INF = 987654321;

int testcase;

int visited[105][105];
int arr[105][105];
int s;

pii rotate(int x, int y)
{
    return { y, s - 1 - x };
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> testcase;

    while (testcase--)
    {
        memset(visited, 0, sizeof(visited));
        memset(arr, 0, sizeof(arr));

        cin >> s;

        rep(i, s)
        {
            string tt;
            cin >> tt;
            rep(j,s)
            {
                arr[i][j] = tt[j] - '0';
            }
        }
        int ans = 0;

        rep(i, s)
        {
            rep(j, s)
            {
                if (visited[i][j] == 1)
                    continue;

                int a = 0;
                int b = 0;
                int curx = j;
                int cury = i;
                for (int r = 0; r < 4; r++)
                {
                    //cout << cury << " " << curx << " " << arr[cury][curx] << "\n";
                    if (arr[cury][curx] == 0)
                        a++;
                    else
                        b++;
                    pii p = rotate(curx, cury);
                    cury = p.second;
                    curx = p.first;
                    visited[cury][curx] = 1;
                }
                //cout << curx << " " << cury << " " << a << " " << b << " " << "\n";
                if (a > b)
                    ans += b;
                else if (a <= b)
                    ans += a;
                
            }
        }
        cout << ans << "\n";
    }


    return 0;
}

 

고찰 :

단순 구현이지만 시계방향으로 회전했을때 좌표의 변환을 처음 알았다.

이 문제 뒤부터는 머리가 굳어버려서 풀 수가 없었다.