Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM530 DIV1 EASY (250pt)
TopCoder SRM530 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

50*50以下のグリッドと,そのサイズ以下のスタンプが与えられる.
グリッドはすでにいくらか黒くて,スタンプは押すと黒くなる場所が与えられる.
スタンプは回転することができず,はみ出して押すことも,すでに黒くなってる場所が,さらに黒くなるようにも押せない.
グリッドを全部黒くすることが出来るかどうかを判定する問題.

解法

greedyにスタンプを左上から押せるだけ押していけば良い.
そして,全部黒くなるかどうかを判定する.
これで良い理由は,グリッドの一番左上の白い場所は,スタンプの一番左上の黒くする場所に対応しなければいけないから.

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 GogoXCake {
public:
string solve(vector <string> now, vector <string> go) {
  int i, j;
  int a, b;
  int x, y, xx, yy;
  int ok;

  x = now.size();
  y = now[0].size();
  xx = go.size();
  yy = go[0].size();

  rep(i,x-xx+1) rep(j,y-yy+1) {
    ok = 1;
    rep(a,xx) rep(b,yy) if(go[a][b]=='.' && now[i+a][j+b]!='.') ok=0;
    if(ok){
      rep(a,xx) rep(b,yy) if(go[a][b]=='.') now[i+a][j+b]='X';
    }
  }

  rep(i,x) rep(j,y) if(now[i][j]=='.') return "NO";
  return "YES";
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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