ABC173-C 備忘録 p.36

itsukiです。
AtCoderの過去問を解いた様子です。解説記事ではありません。

C - H and V

考察の流れ

0行目を塗る or 塗らない、・・・、H行目を塗る or 塗らない
0列目を塗る or 塗らない、・・・、W列目を塗る or 塗らない
上記それぞれについて考えるので、bit全探索の入れ子？

（過去に書いた bit全探索のソースを引っ張り出してくる）

書いているうちに for文が 4重になってしまう
1 <= H, W <= 6 なので間に合うだろうけど、混乱する

特定の行列を 塗る or 塗らないときに、
任意の c_i,j が塗られていない　かつ　c_i,j が黒マスである場合をカウント

カウント数が K個 のとき、
「操作後に黒いマスがちょうど K個残るような行と列の選び方」となる

#include <stdio.h>
int main(){
   int h,w,k,cnt=0,ans=0;
   scanf("%d%d%d",&h,&w,&k);
   char c[7][7]={0};
   for(int i=0; i<h; i++){ scanf("%s",c[i]); }
   
   // h行を塗る塗らない
   for(int hb=0; hb<(1<<h); hb++){
       // w列を塗る塗らない
       for(int wb=0; wb<(1<<w); wb++){

           for(int i=0; i<h; i++){
               for(int j=0; j<w; j++){
                   // Cij が塗られていない　かつ　黒
                   if( !(hb & (1<<i)) && !(wb & (1<<j)) ){
                       if( c[i][j]=='#' ){ cnt++; }
                   }
               }
           }
           if( cnt==k ){ ans++; }
           cnt  = 0;
       }
   }
   printf("%d\n",ans);
   return 0;
}

まとめ

・過去のソースを引っ張り出さないと、bit全探索が書けないことに気づく
・もし全探索するとTLEするような条件だったら、どうすればいいか分からない…
・for文が 4重になっても考え続けられたのは良かった（諦めそうになった）

引き続き、のんびり精進します。

#備忘録 #AtCoder #ABC #競技プログラミング #競プロ #C言語 #bit全探索