Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM533 DIV1 MEDIUM - MagicBoard (この記事を編集する[管理者用])

Source

TopCoder SRM533 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

n*m (50*50以下) のグリッドが与えられる.各セルは#か.のどちらか.
好きな#のセルから初めて良いので,以下のような方法で,すべての#を削除できるかどうかを判定する問題.
 今いる場所の#を消し,
  現在の処理の回数が偶数回目なら,今と同じ行の#のセルに移動する.
  現在の処理の回数が奇数回目なら,今と同じ列の#のセルに移動する.
 最初に動くのは,0回目とする.(最初は同じ行内で動く)

解法

2つセットで考えると,X = #が奇数個ある行の数,Y = #が奇数個ある列の数とすると,
 Xは0以上1以下,Yは0以上2以下
を満たさなければいけないことがわかる.
また,自由に同じ行,同じ列にある#まで動くことができるとすると,すべての#のセルは連結でなければいけない.
逆に,以上の条件を満たせば,必ずすべての#を通るパスが存在することを示すことができる.

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

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

void unionInit(int d[],int s){int i;rep(i,s)d[i]=i;}
int unionGet(int d[],int n){int t=n,k;while(d[t]!=t)t=d[t];while(d[n]!=n)k=d[n],d[n]=t,n=k;return n;}
int unionConnect(int d[],int a,int b){a=unionGet(d,a);b=unionGet(d,b);if(a==b)return 0;d[a]=b;return 1;}

int ind[3000];

class MagicBoard {
public:
string ableToUnlock(vector <string> in) {
  int i,j,k;
  int x,y,bef;
  int X[100], Y[100], Xodd, Yodd;
  string res;

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

  rep(i,100) X[i] = Y[i] = 0;
  rep(i,x) rep(j,y) if(in[i][j] == '#'){
    X[i]++;
    Y[j]++;
  }

  Xodd = Yodd = 0;
  rep(i,x) if(X[i]%2) Xodd++;
  rep(i,y) if(Y[i]%2) Yodd++;

  if(Xodd > 1 || Yodd > 2) return "NO";

  unionInit(ind, x*y);
  rep(i,x){
    rep(j,y) if(in[i][j]=='#') REP(k,j+1,y) if(in[i][k]=='#') unionConnect(ind, i*y+j, i*y+k);
  }
  rep(i,y){
    rep(j,x) if(in[j][i]=='#') REP(k,j+1,x) if(in[k][i]=='#') unionConnect(ind, j*y+i, k*y+i);
  }
  rep(i,x*y) unionGet(ind, i);

  bef = -1;
  rep(i,x) rep(j,y) if(in[i][j]=='#'){
    k = unionGet(ind, i*y+j);
    if(bef == -1) bef = k;
    if(bef != k) return "NO";
  }
  
  return "YES";
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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