Submission #00048

ソースコード

#include<bits/stdc++.h>
using namespace std;
struct edge {
  int to, cost;
};
typedef pair< int, int > Pi;
const int INF = 1 << 30;
 
 
int h, w;
int sx, sy, gx, gy;
int n;
Pi mas[31][31];
int m;
int bit[31][31];
 
 
const int dy[] = {0, 0, 1, 0, -1}, dx[] = {0, 1, 0, -1, 0};
 
bool used[31][31][5][1 << 10];
 
bool rec(int x, int y, int d, int bits)
{
  if(x < 0 || x >= w || y < 0 || y >= h) return(false);
  if(used[x][y][d][bits]++) return(false);
  if(x == gx && y == gy) return(true);
  int ret = 0;
  if(d == 0) {
    for(int i = 1; i < 5; i++) {
      if(rec(x + dx[i], y + dy[i], i, bits)) return(true);
    }
    return(false);
  } else {
    if(mas[y][x] == Pi(-1, -1)) {
      return(rec(x - dx[d], y - dy[d], 0, bits));
    }
    if(mas[y][x] != Pi(INF, INF)) {
      Pi prev = Pi(INF, INF);
      Pi curr = Pi(INF, INF);
      swap(prev, mas[y][x]);
      swap(curr, mas[prev.first][prev.second]);
      if(rec(prev.first, prev.second, 0, bits|(1 << bit[y][x]))) return(true);
      swap(prev, mas[y][x]);
      swap(curr, mas[prev.first][prev.second]);
      return(false);
    }
    return(rec(x + dx[d], y + dy[d], d, bits));
  }
}
 
 
int main()
{
 
  fill_n(*mas, 31 * 31, make_pair(INF, INF));
 
  cin >> h >> w;
  cin >> sx >> sy >> gx >> gy;
  cin >> n;
  int tail = 0;
 
  for(int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    mas[b][a] = make_pair(-1, -1);
  }
  cin >> m;
 
  for(int i = 0; i < m; i++) {
    int ax, ay, bx, by;
    cin >> ax >> ay >> bx >> by;
    if(mas[ay][ax] == make_pair(-1, -1)) throw(0);
    if(mas[by][bx] == make_pair(-1, -1)) throw(0);
    mas[ay][ax] = make_pair(by, bx);
    mas[by][bx] = make_pair(ay, ax);
    bit[by][bx] = tail;
    bit[ay][ax] = tail;
    ++tail;
  }
  if(rec(sx, sy, 0, 0)) puts("OK");
  else puts("NO");
}

ステータス

項目	データ
問題	0003 - 滑った故の結末
ユーザー名	ei1333
投稿日時	2015-09-16 18:00:59
言語	C++11
状態	Runtime Error
得点	0
ソースコード長	1867 Byte
最大実行時間	38 ms
最大メモリ使用量	656 KB

セット

	セット	得点	Cases
1	ALL	0 / 100	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
dfs-b_in1.txt	RE	38 ms	476 KB	1
dfs-b_in2.txt	AC	19 ms	600 KB	1
dfs-b_in3.txt	RE	22 ms	620 KB	1
dfs-b_in4.txt	AC	21 ms	420 KB	1
dfs-b_in5.txt	RE	26 ms	496 KB	1
dfs-b_in6.txt	RE	24 ms	568 KB	1
dfs-b_in7.txt	RE	24 ms	532 KB	1
dfs-b_in8.txt	AC	22 ms	476 KB	1
dfs-b_in9.txt	AC	18 ms	552 KB	1
dfs-b_in10.txt	AC	29 ms	616 KB	1
dfs-b_in11.txt	RE	29 ms	656 KB	1