Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Round #209 DIV2 E問題 - Neatness (この記事を編集する[管理者用])

Source

Codeforces Round #209 DIV2 E問題 (2500pt)
Problem description

問題概要

縦横 $n$ マスのグリッドが与えられる.
各セルは部屋で,合計 $n^2$ 個の部屋がある.
最初,各部屋が電気が付いているかどうかが与えられる.
また,最初にいる部屋の位置 $(x_0,\ y_0)$ が与えられる.
全ての部屋の電気を消した上で,最初いた部屋に戻る方法を $1$ つ求める問題.
手順数は最小である必要はないが,手順数は $3 \times 10^6$ 以下でなければならない.
できる手順は以下の通り:
 上下左右にずっと進んだ方向に,$1$ つ以上電気がついた部屋があるなら,上下左右に $1$ マス移動できる
 今いる部屋の電気をつける,もしくは,消す
なお,不可能ならそれを指摘する.

解法

DFSで行けるセルを全て巡る.
その際,初めてそのセルに到着した時に,電気がついていないなら電気をつけ,
最後にそのセルから立ち去るときに,電気を消していけば良い.
以下の解答では,$1$ 回目のDFSで電気をつけて回って,$2$ 回目のDFSで電気を消して回った.

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, stx, sty;
int mp[510][510];

char res[5000000];
int res_size;

int di[4]={-1,0,1,0};
int dj[4]={0,-1,0,1};
char dir[10] = "ULDR";

int visited[510][510];

int is_light(int i, int j, int di, int dj){
  for(;;){
    if(i < 0 || j < 0 || i >= x || j >= y) break;
    if(mp[i][j]==1) return 1;
    i += di; j += dj;
  }
  return 0;
}

void dfs1(int i, int j){
  int ni, nj, k;

  visited[i][j] = 1;
  if(!mp[i][j]){
    mp[i][j] = 1;
    res[res_size++] = '1';
  }
  rep(k,4){
    ni = i+di[k]; nj = j+dj[k];
    if(ni < 0 || nj < 0 || ni >= x || nj >= y || visited[ni][nj]) continue;
    if(!is_light(ni,nj,di[k],dj[k])) continue;
    res[res_size++] = dir[k];
    dfs1(ni, nj);
    res[res_size++] = dir[(k+2)%4];
  }
}

void dfs2(int i, int j){
  int ni, nj, k;

  visited[i][j] = 1;
  rep(k,4){
    ni = i+di[k]; nj = j+dj[k];
    if(ni < 0 || nj < 0 || ni >= x || nj >= y || visited[ni][nj]) continue;
    if(!is_light(ni,nj,di[k],dj[k])) continue;
    res[res_size++] = dir[k];
    dfs2(ni, nj);
    res[res_size++] = dir[(k+2)%4];
  }

  mp[i][j] = 0;
  res[res_size++] = '2';
}

int main(){
  int i, j, k;

  scanf("%d%d%d",&x,&stx,&sty);
  y = x; stx--; sty--;
  rep(i,x) rep(j,y) scanf("%d",mp[i]+j);

  res_size = 0;

  rep(i,x) rep(j,y) visited[i][j] = 0;
  dfs1(stx,sty);

/*  puts("mp after dfs1");
  rep(i,x){ rep(j,y) printf("%d ",mp[i][j]); puts(""); }
  puts("visted after dfs1");
  rep(i,x){ rep(j,y) printf("%d ",visited[i][j]); puts(""); }*/

  k = 0;
  rep(i,x) rep(j,y){
    if(mp[i][j] && !visited[i][j]) k++;
  }
  if(k){ puts("NO"); return 0; }

  rep(i,x) rep(j,y) visited[i][j] = 0;
  dfs2(stx,sty);
  
  res[res_size] = '\0';
  puts("YES");
  printf("%s\n",res);

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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