[BaekJun, C++] 1018: Repainting a Chess Board

 

https://www.acmicpc.net/problem/1018

Problem

Jimin found an M×N sized board in his mansion that is divided into MN unit squares. Some of these squares are painted black, while the rest are white. Jimin wants to cut the board into 8×8-sized chessboards.

A chessboard must have alternating black and white squares. Specifically, each cell should be painted either black or white, and two squares sharing an edge must have different colors. Therefore, there are only two ways to color the chessboard. One has the top-left square white, and the other has it black.

There is no guarantee that the board is already colored like a chessboard, so Jimin plans to cut it into 8×8 pieces and repaint some of the squares. Naturally, he can choose the 8×8 sections from anywhere. Your task is to write a program that calculates the minimum number of squares that Jimin needs to repaint.

Input

The first line contains two integers, N and M. N and M are natural numbers greater than or equal to 8 and less than or equal to 50. From the second line onwards, there are N lines representing the state of each row of the board. B stands for black, and W stands for white.

Output

The first line should output the minimum number of squares that Jimin needs to repaint.

#include <iostream> #include <string> #include <vector> //Vector in C++ using namespace std; string WB[8] = {//It's easier to compare the boards with pre-made boards "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW" }; string BW[8] = { "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB" }; string board[50]; int WB_cnt(int x, int y){ int cnt = 0; for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { if (board[x + i][y + j] != WB[i][j]) cnt++; } } return cnt; } int BW_cnt(int x, int y) { int cnt = 0; for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { if (board[x + i][y + j] != BW[i][j]) cnt++; } } return cnt; } int main() { int cnt; int min_val = 12345; pair<int, int> p1; // included in the vector header file cin >> p1.first >> p1.second; for (int i = 0; i < p1.first; i++) cin >> board[i]; for (int i = 0; i + 8 <= p1.first; i++) {//access with .first .second for pairs for (int j = 0; j + 8 <= p1.second; j++) { int tmp; tmp = min(WB_cnt(i, j), BW_cnt(i, j)); if (tmp < min_val) { min_val = tmp; } } } cout << min_val; return 0; }

The vector in C++ is a class in the C++ Standard Template LIbrary(STL) to use as a sort of container

When you create a vecotr, it's memory is allocated in the heap dynamically.

The Pair Class is a STL included in the #include <utility> header file

but it's already included in the algorithm and vector header files so you cans just do #include <vector> and use pair 

In conclusion this was a BruteForce problem where you have to look at every case.

Comments

Post a Comment

Popular posts from this blog

Binary Search: The Efficient Solution for Sorted Arrays

Image
Binary Search is a powerful algorithm that allows you to efficiently search for a target element within a sorted array. This algorithm works by repeatedly dividing the search space in half, which makes it an extremely efficient method for finding elements in large, ordered datasets. The Prerequisite: Sorted Array Before we dive into the details of Binary Search, it's important to understand that this algorithm can only be applied to sorted arrays. If the array is not sorted, Binary Search will not work correctly, and you may end up with incorrect results. The reason for this requirement is that Binary Search relies on the fact that the array is already in order. This allows the algorithm to make informed decisions about which half of the array to search next, based on the comparison between the target element and the middle element of the current search space. The Binary Search Algorithm The Binary Search algorithm follows these steps: 1. Initialize the search space: Set the lowe...
Read more

[BaekJun,C++]1929: finding primes

Image
  https://www.acmicpc.net/problem/1929 Problem: Write a program that prints all prime numbers between M and N, inclusive. Input: The natural numbers M and N are given on the first line, separated by a space. (1 ≤ M ≤ N ≤ 1,000,000) The input guarantees that there is at least one prime number between M and N. Output: Print the prime numbers in ascending order, one per line. #include < iostream > #include < cstdio > #include < algorithm > using namespace std; int m, n; int main(void) { cin >> m >> n; int size = n - m + 1; int* prime = new int[n + 1]; prime[1] = 0; for (int i = 2; i < n + 1; i++) { prime[i] = 1; } //eratostheneses sieve for (int i = 2; i < n + 1;i++) { if (prime[i] == 0) { continue;// continue, break } else { for (int j = i * 2; j < n + 1; j += i) { //you don't always have to incerase the index by 1 prime[j] = 0; } } ...
Read more