結果

問題 No.331 CodeRunnerでやれ
ユーザー naimonon77naimonon77
提出日時 2016-02-27 11:35:13
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 395 ms / 5,000 ms
コード長 3,621 bytes
コンパイル時間 1,431 ms
コンパイル使用メモリ 155,236 KB
実行使用メモリ 42,048 KB
平均クエリ数 321.41
最終ジャッジ日時 2023-09-23 23:16:17
合計ジャッジ時間 6,575 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 131 ms
23,880 KB
testcase_01 AC 134 ms
23,508 KB
testcase_02 AC 158 ms
24,040 KB
testcase_03 AC 157 ms
23,416 KB
testcase_04 AC 166 ms
24,216 KB
testcase_05 AC 163 ms
24,036 KB
testcase_06 AC 222 ms
42,048 KB
testcase_07 AC 268 ms
23,476 KB
testcase_08 AC 162 ms
24,304 KB
testcase_09 AC 271 ms
23,416 KB
testcase_10 AC 207 ms
23,668 KB
testcase_11 AC 197 ms
23,368 KB
testcase_12 AC 233 ms
24,172 KB
testcase_13 AC 249 ms
24,180 KB
testcase_14 AC 395 ms
37,872 KB
testcase_15 AC 253 ms
24,028 KB
testcase_16 AC 294 ms
23,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <vector>
#include <queue>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
using namespace std;
#define SIZE 50
enum Muki{
  up,r,down,l
};
bool test = 0;
void draw_map(char map[][SIZE],int a,int x, int y,int muki) {
  int i;
  for(i=1;i<a+1;i++) {
    switch(muki) {
    case  up  : map[ x ][y+i] = '.'; break;
    case down : map[ x ][y-i] = '.'; break;
    case   r  : map[x+i][ y ] = '.'; break;
    case   l  : map[x-i][ y ] = '.'; break;
    }
  }
  switch(muki) {
  case  up  : map[ x ][y+i] = '#'; break;
  case down : map[ x ][y-i] = '#'; break;
  case   r  : map[x+i][ y ] = '#'; break;
  case   l  : map[x-i][ y ] = '#'; break;
  }
  // map[x][y] = '!';
}
class Route1{
public:
  vector<int> route;
  bool visited[SIZE][SIZE];
  int x,y;
  int index;
  Route1() {
    int i,j;
    rep(i,SIZE) {
      rep(j,SIZE) visited[i][j] = false;
    }
  }
};

bool map_search(char map[][SIZE],
  int x,int y,queue<Route1>& q,const Route1& now) 
{
  if( (not now.visited[x][y]) && map[x][y] != '#' ) {
    Route1 next = now;
    next.x = x , next.y = y;
    next.visited[x][y] = true;
    q.push(next);
    return true;
  }
  return false;
}

// 最も近い分からない場所を探索
// 最後は行けるか分からない
Route1 wfs(char map[][SIZE],int x,int y) {
  bool test = 0;
  queue< Route1 > q;
  Route1 now;
  now.x = x; now.y = y;
  now.index = 0;
  now.visited[x][y] = true;
  q.push(now);
  while( q.size() ) {
    now = q.front(); q.pop();
    int x = now.x , y = now.y;
    if(test) printf("map[%d][%d] = %c",x,y,map[x][y]);
    if(test) puts("");
    if(map[x][y] == 0) {
      return now;
    }
    if( map_search(map,x-1, y ,q,now) ) {
      q.back().route.push_back(l);
    }
    if( map_search(map,x+1, y ,q,now) ) {
      q.back().route.push_back(r);
    }
    if( map_search(map, x ,y-1,q,now) ) {
      q.back().route.push_back(down);
    }
    if( map_search(map, x ,y+1,q,now) ) {
      q.back().route.push_back(up);
    }
  }
  exit(1);
}

void player_move(int muki,int& x,int& y,
  char map[][SIZE]) 
{
  map[x][y] = '.';
  switch(muki) {
  case  up : y++; map[x][y] = '^'; break;
  case down: y--; map[x][y] = 'v'; break;
  case  r  : x++; map[x][y] = '>'; break;
  case  l  : x--; map[x][y] = '<'; break;
  }
}

void muki_draw(int muki,int& x,int& y,
  char map[][SIZE]) 
{
  switch(muki) {
  case  up : map[x][y] = '^'; break;
  case down: map[x][y] = 'v'; break;
  case  r  : map[x][y] = '>'; break;
  case  l  : map[x][y] = '<'; break;
  }
}

int main() {
  /*
  cin.tie(0);
  ios::sync_with_stdio(false);
  */
  bool test = 1;
  char map[SIZE][SIZE] = {0};  // 0 or '.' or '#'
  int x = SIZE/2 ,y = SIZE/2;
  int muki = down;
  char s[20];
  Route1 route1;
  route1.index = 0;
  if(test) muki_draw(muki,x,y,map);
  while(cin >> s) {
    char c;
    if(strcmp(s,"Merry") == 0)  break;
    int a = atoi(s);
    if(a > 50) {
      c = 'F';
      player_move(muki,x,y,map);
    }
    else {
      draw_map(map,a,x,y,muki);
      int& index = route1.index;
      if(a == 0 or route1.route.size() == index) {
        route1 = wfs(map,x,y);
        /*if(test) {
          int i;
          REP(i,index,route1.route.size() ){
            cout << muki_convert(route1.route[i]);
          }
          puts("");
        }*/
      }
      if(a != 0 && route1.route[index] == muki) {
        player_move(muki,x,y,map);
        c = 'F';
        index++;
      }
      else {
        c = 'L';
        muki--;
        if(muki < up) muki = l;
        if(test) muki_draw(muki,x,y,map);
      }
    }
    cout << c << endl;
  }
  cin >> s;
  return 0;
}
0