白準-1018チェス盤を塗り直す


碁盤を塗り直す


志敏は自分の屋敷でMNサイズの碁盤を見つけた.一部の正方形は黒に塗り、残りは白に塗ります.志敏はこの碁盤を88ヤードのチェス盤に切ろうとした.
チェスの碁盤は白黒の間にあるべきだ.具体的には、各セルは白黒の1つに塗り、共有エッジの2つの長方形は異なる色に塗ります.したがって,この定義によれば,チェス盤が色付く場合は2つしかない.一つは左上の格子が白で、一つは黒です.
碁盤がチェス盤のようにペンキが塗られている保証はないので、志敏は碁盤を88ヤードの大きさに切り、正方形を何枚か塗りたいと思っています.88の大きさはもちろん自由に選べます.プログラムを書いて、志敏が塗り直す正方形の最小個数を求めます.

✔方法


すべての可能性を検出するルーティング転送アルゴリズムを利用する.
  • 入力チェス盤から8*8部
  • を抽出
  • 左上隅格子に基づいてB chess,W chessの条件と現在の部分碁盤格子を比較し,再塗工が必要な正方形の個数
  • を算出した.
  • 出力最小値
  • ✔コード

    #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;
    }

    チップ

  • B chess,W chessの2つの方法が考えられるため,constで8*8チェス版を事前定義し,比較と直感的なコードを記述することができる.
  • 再試行✔コード

    #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題