Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #11 C問題 - How Many Squares? (この記事を編集する[管理者用])

Source

Codeforces Beta Round #11 C問題
Problem description
Beta Round #11の自分の参加記録

問題概要

01からなる250*250以下のグリッドが与えられる.
並行か,斜め45度のサイズ2以上の1からなる正方形の数を数える問題.
ただし,正方形は,その他の1に縦横斜めで接していてはいけない.

解法

連結している1の集合を持ってきて,逐次それが正方形をなしているかどうかを判定してやれば良い.
正方形をなしているならば,1の数は4*(正方形の一辺の長さ-1)なので,それで正方形のサイズを判定してやって,対応する場所に全部1があるかどうかを調べれば良い.

C言語のスパゲッティなコード

このコードは実際に本番でサブミットしたコードです.見にくいと思われます.

#include<stdio.h>
#include<stdlib.h>
#include<math.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[300][300];

int cnt;

void nul(int a,int b,char from,char to){
  int i,j;
  if(a<0||b<0||a>=x||b>=y||in[a][b]!=from) return;
  cnt++; in[a][b]=to;
  REP(i,-1,2) REP(j,-1,2) nul(a+i,b+j,from,to);
}

int is_ok(int i,int j){
  if(i<0||j<0||i>=x||j>=y||in[i][j]!='2') return 0;
  return 1;
}

int main(){
  int i,j,k,l,m,n,len,ok,res;
  int size;

  scanf("%d",&size);
  while(size--){
    scanf("%d%d",&x,&y);
    rep(i,x) scanf("%s",in[i]);
    res=0;

    rep(i,x) rep(j,y) if(in[i][j]=='1'){
      cnt=0; nul(i,j,'1','2');
      if(cnt%4==0){
        len = cnt/4 + 1;

        ok=1;
        rep(k,len) if( !is_ok(i+k,j) ) ok=0;
        rep(k,len) if( !is_ok(i,j+k) ) ok=0;
        rep(k,len) if( !is_ok(i+len-1,j+k) ) ok=0;
        rep(k,len) if( !is_ok(i+k,j+len-1) ) ok=0;
        res += ok;

        ok=1;
        rep(k,len) if( !is_ok(i+k,j+k) ) ok=0;
        rep(k,len) if( !is_ok(i+k,j-k) ) ok=0;
        rep(k,len) if( !is_ok(i+2*len-2-k,j+k) ) ok=0;
        rep(k,len) if( !is_ok(i+2*len-2-k,j-k) ) ok=0;
        res += ok;
      }
      nul(i,j,'2','0');
    }

    printf("%d\n",res);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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