Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2319-35bd1fbe
この記事にトラックバックする(FC2ブログユーザー)

ARC 006 D - アルファベット探し (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #006
問題文

問題概要

H*W (1000*1000以下) のグリッドが与えられ,各セル白か黒.
アルファベットのABCがいくらか書かれている.
アルファベットは90度の整数倍回転してるかもしれず,鏡像反転してるかもしれず,正整数倍拡大しているかもしれない.
ただし,アルファベットは重なっておらず,アルファベットに属さない黒いセルもない.
ABCがそれぞれ何個書かれているか求める問題.

解法

色々やりかたはあると思う.
縦横斜めに連結と思い,各連結成分ごとに黒のセルの数を数え,例えば,その数が12*k^2の形ならAとする,などと判定した.

Cによるスパゲッティなソースコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int x, y;
char in[2100][2100];

int st[4000000], st_size;

int main(){
  int i,j,k,l,m,n;
  int si, sj, ni, nj, di, dj;
  int res[3], cnt;

  scanf("%d%d",&x,&y);
  rep(i,x) scanf("%s",in[i]);

  rep(i,3) res[i] = 0;

  rep(i,x) rep(j,y) if(in[i][j]=='o'){
    cnt = 1;
    st_size = 1;
    st[0] = i*y + j;
    in[i][j] = '.';

    while(st_size){
      k = st[--st_size];
      si = k/y; sj = k%y;
      REP(di,-1,2) REP(dj,-1,2){
        ni = si+di;
        nj = sj+dj;
        if(ni < 0 || nj < 0 || ni >= x || nj >= y || in[ni][nj]!='o') continue;
        in[ni][nj] = '.';
        st[st_size++] = ni*y + nj;
        cnt++;
      }
    }

    for(k=1;;k++){
      if(cnt % (k*k)) continue;
      m = cnt / (k*k);
      if(m==12){ res[0]++; break; }
      if(m==16){ res[1]++; break; }
      if(m==11){ res[2]++; break; }
    }
  }

  printf("%d %d %d\n",res[0],res[1],res[2]);

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2319-35bd1fbe
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。