Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM496 DIV1 EASY/DIV2 MEDIUM - ColoredStrokes (この記事を編集する[管理者用])

Source

TopCoder SRM496 DIV1 EASY (250pt)
TopCoder SRM496 DIV2 MEDIUM (500pt)
Problem Statement
SRM496 DIV1 自分の参加記録

問題概要

50*50以下のグリッドが与えられる.各グリッドは赤,緑,青,白のどれか.
1回で,青は横幅1マスで縦にいくらでも長く塗れる.
1回で,赤は縦幅1マスで横にいくらでも長く塗れる.
緑は赤青両方で塗られたマス.
真っ白の盤面から,与えられたグリッドを作るための最小塗り回数を求める問題.

解法

赤と青は別々に考えれば良い.
それぞれ塗れるだけ長く塗れば良いので,縦か横の線分がいくつ存在するか数えるだけ.
他の人の解法で賢いなと思った実装方法は,横の線の数を数えるなら,横方向に塗る場所と塗らない場所が隣り合ってる部分の数を数えれば良い,という実装.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

class ColoredStrokes {
public:
int getLeast(vector <string> mp) {
  int i,j,k,x,y;
  int res = 0;

  x = mp.size();
  y = mp[0].size();

  rep(i,x) rep(j,y){
    if(mp[i][j]=='.'){ mp[i][j]=0; continue; }
    if(mp[i][j]=='B'){ mp[i][j]=1; continue; }
    if(mp[i][j]=='R'){ mp[i][j]=2; continue; }
    if(mp[i][j]=='G'){ mp[i][j]=3; continue; }
  }

  rep(i,x) rep(j,y) if(mp[i][j]&1){
    res++;
    REP(k,i,x) if(mp[k][j]&1) mp[k][j]^=1; else break;
  }
  rep(i,x) rep(j,y) if(mp[i][j]&2){
    res++;
    REP(k,j,y) if(mp[i][k]&2) mp[i][k]^=2; else break;
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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