Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #94 DIV1 A問題/DIV2 C問題 - Statues (この記事を編集する[管理者用])

Source

Codeforces Beta Round #94 DIV1 A問題 (1000pt)
Codeforces Beta Round #94 DIV2 C問題 (2000pt)
Problem description

問題概要

8*8のチェス盤で,最初,自分は一番左下にいる.
いくつかのセルには障害物がある.
毎ターン,
 自分が上下左右斜め障害物のない場所に移動する.もしくは動かない.
 その後,障害物が一斉に1マス下に移動する.自分が潰されたら死ぬ.
一番右上のセルに辿りつけるかどうかを求める問題.

解法

7ターンぐらい生き残れば,障害物はいなくなって,勝てるし,辿り着くまでに7ターンぐらいかかるので,7ターン生き残れなければ勝てない.
全探索なり,DPなりで7ターン後に生き残れているかどうかを調べる.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int x, y;
char mp[10][10], next[10][10];
int ok[10][10], go[10][10];

int main(){
  int i,j,k,l,m,n;
  int ii, jj, iii, jjj;
  int loop;

  x = y = 8;
  for(;;){
    k = 0;
    rep(i,x) k += scanf("%s",mp[i]);
    if(k!=x) break;

    mp[0][7] = mp[7][0] = '.';
    rep(i,x) rep(j,y) ok[i][j] = 0; ok[7][0] = 1;

    rep(loop,50){
/*      printf("turn %d\n",loop);
      rep(i,x){ rep(j,y) printf("%d ",ok[i][j]); puts(""); } puts("");*/
      
      rep(i,x) rep(j,y) go[i][j] = 0;
      
      rep(i,x) rep(j,y) if(ok[i][j]) REP(ii,-1,2) REP(jj,-1,2){
        iii = i + ii;
        jjj = j + jj;
        if(iii < 0 || jjj < 0 || iii >= x || jjj >= y) continue;
        if(mp[iii][jjj] == 'S') continue;
        go[iii][jjj] = 1;
      }

      rep(i,x) rep(j,y) next[i+1][j] = mp[i][j];
      rep(j,y) next[0][j] = '.';
      rep(i,x) rep(j,y) if(go[i][j] && next[i][j]=='S') go[i][j] = 0;


      rep(i,x) rep(j,y) mp[i][j] = next[i][j];
      rep(i,x) rep(j,y) ok[i][j] = go[i][j];

      if(ok[0][7]) break;
    }

    if(loop==50)puts("LOSE"); else puts("WIN");
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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