Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

2010 Round 1A A問題 - Rotate (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1A A問題
Problem Statement
2010 Round 1A 自分の参加記録

問題概要

N*NのグリッドにRかBの文字が書いてある.重力によって,文字は下に落ちている.
90度時計回りに回転させる.文字は重力によって下に落ちる.
縦横斜め,一直線上にRとBがそれぞれK個以上繋がっている場所があるかどうかを,それぞれ判定する問題.
small: Nは7以下
large: Nは50以下

解法

実装するだけ.サイズは小さいので愚直な方法で大丈夫.
(実際に回転させなくても,右に寄せるでもOK)

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 n, m;
char in[60][60], tmp[60][60];

int solve(char c){
  int i,j,k,dx,dy;
  int ni, nj;

  rep(i,n) rep(j,n) REP(dx,-1,2) rep(dy,2) if(dx||dy){
    k=0;
    ni=i; nj=j;
    for(;;){
      if(ni<0||nj<0||ni>=n||nj>=n||in[ni][nj]!=c) break;
      k++; ni+=dx; nj+=dy;
    }
    if(k >= m) return 1;
  }
  return 0;
}

int main(){
  int i,j,k,l;
  int fg1, fg2;
  int size,count=0;

  scanf("%d",&size);
  while(size--){
    scanf("%d%d",&n,&m);
    rep(i,n) scanf("%s",tmp[i]);

    rep(i,n) rep(j,n) in[j][n-1-i]=tmp[i][j];

    rep(j,n){
      k=n-1;
      for(i=n-1;i>=0;i--) if(in[i][j]!='.') in[k][j]=in[i][j], k--;
      while(k>=0) in[k][j]='.', k--;
    }

    fg1 = solve('R');
    fg2 = solve('B');

    printf("Case #%d: ",++count);
    if( fg1 &&  fg2) puts("Both");
    if( fg1 && !fg2) puts("Red");
    if(!fg1 &&  fg2) puts("Blue");
    if(!fg1 && !fg2) puts("Neither");
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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