白準-1018チェス盤を塗り直す
29209 ワード
碁盤を塗り直す
志敏は自分の屋敷でMNサイズの碁盤を見つけた.一部の正方形は黒に塗り、残りは白に塗ります.志敏はこの碁盤を88ヤードのチェス盤に切ろうとした.
チェスの碁盤は白黒の間にあるべきだ.具体的には、各セルは白黒の1つに塗り、共有エッジの2つの長方形は異なる色に塗ります.したがって,この定義によれば,チェス盤が色付く場合は2つしかない.一つは左上の格子が白で、一つは黒です.
碁盤がチェス盤のようにペンキが塗られている保証はないので、志敏は碁盤を88ヤードの大きさに切り、正方形を何枚か塗りたいと思っています.88の大きさはもちろん自由に選べます.プログラムを書いて、志敏が塗り直す正方形の最小個数を求めます.
✔方法
すべての可能性を検出するルーティング転送アルゴリズムを利用する.
✔コード
#include <stdio.h>
int main(void){
int row=0, col=0;
char board[50][50] = {0,};
char tmp;
int r_start=0, c_start=0, count1=0, count2=0, min=999999;
char check;
scanf("%d %d\n", &row, &col);
for(int i=0; i<row; i++){
for( int j=0; j<col; j++){
while(1){
tmp = getchar();
if (tmp != '\n'){
board[i][j] = tmp;
break;
}
}
}
}
/* 전체 체스판에서 8*8 부분 체스판을 취함 */
for(int i=0; i<=row-8; i++){
for(int j=0; j<=col-8; j++){
check = board[i][j]; // 부분 체스판의 맨왼쪽위 칸의 색
/* 8*8 부분 체스판에서 색이 다른 부분의 갯수를 확인 */
for(int k=0; k<8; k++){
for (int l=0; l<8; l++){
if ( k%2==0 && l%2==0 ){
if( board[i+k][j+l] != check ){ // 맨 왼쪽위 색으로 시작한 체스판
count1++;
}
else{ // 반대의 경우 체스판
count2++;
}
}
else if( k%2==0 && l%2==1 ) {
if( board[i+k][j+l] == check ){
count1++;
}
else{
count2++;
}
}
else if( k%2==1 && l%2==0 ) {
if( board[i+k][j+l] == check ){
count1++;
}
else{
count2++;
}
}
else if( k%2==1 && l%2==1 ) {
if( board[i+k][j+l] != check ){
count1++;
}
else{
count2++;
}
}
}
}
if( count1 <= count2 ){
if( min > count1 ){
min = count1;
}
}
else{
if( min > count2 ){
min = count2;
}
}
count1 = 0;
count2 = 0;
}
}
printf("%d\n", min);
return 0;
}
チップ
再試行✔コード
#include <stdio.h>
#include <string>
#include <algorithm>
using namespace std;
const string b_chess[8] = {
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
};
const string w_chess[8] = {
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
};
int main(void){
int row=0, col=0;
char board[50][50] = {0,};
char tmp;
int r_start=0, c_start=0, count1=0, count2=0, min_result=999999;
char check;
scanf("%d %d\n", &row, &col);
for(int i=0; i<row; i++){
for( int j=0; j<col; j++){
while(1){
tmp = getchar();
if (tmp != '\n'){
board[i][j] = tmp;
break;
}
}
}
}
/* 전체 체스판에서 8*8 부분 체스판을 취함 */
for(int i=0; i<=row-8; i++){
for(int j=0; j<=col-8; j++){
check = board[i][j]; // 부분 체스판의 맨왼쪽위 칸의 색
/* 8*8 부분 체스판에서 색이 다른 부분의 갯수를 확인 */
for(int k=0; k<8; k++){
for (int l=0; l<8; l++){
if( board[i+k][j+l] != b_chess[k][l] ){ count1++; }
if( board[i+k][j+l] != w_chess[k][l] ){ count2++; }
}
}
// printf("[check] %d %d\n", count1, count2);
if (min_result > min(count1, count2)){
min_result = min(count1, count2);
}
count1 = 0;
count2 = 0;
}
}
printf("%d\n", min_result);
return 0;
}
👍 コメントサイト
白駿13549題
Reference
この問題について(白準-1018チェス盤を塗り直す), 我々は、より多くの情報をここで見つけました https://velog.io/@aszxvcb/백준-1018テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol