Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM394 DIV2 EASY - MountainWalk (この記事を編集する[管理者用])

Source

TopCoder SRM394 DIV2 EASY (250pt)
Problem Statement

問題概要

50*50以下のグリッドの標高が与えられる.
最初左上にいて,下,左,上,右の4方向セルのうち,移動できる最初のセルに移動する.
移動できるセルは,まだ行ったことがなくて,標高差がheightDifference以下のセル.
最終的に何セルに辿りつけるかを求める問題.

解法

やるだけ.

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

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

int ab(int a){if(a<0)return -a; return a;}

class MountainWalk {
public:
int cellsVisited(vector <string> mp, int dif) {
  int i,j,k;
  int x=mp.size(),y=mp[0].size(),dx[4]={1,0,-1,0},dy[4]={0,-1,0,1};
  int sx=0,sy=0,nx,ny;
  int reach[60][60]={1};
  int res;

  for(;;){
    rep(k,4){
      nx=sx+dx[k]; ny=sy+dy[k];
      if(nx<0||ny<0||nx>=x||ny>=y||reach[nx][ny]) continue;
      if(ab(mp[nx][ny]-mp[sx][sy]) > dif) continue;
      reach[nx][ny]=1; sx=nx; sy=ny; break;
    }
    if(k==4) break;
  }

  res=0;
  rep(i,x) rep(j,y) res += reach[i][j];

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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