結果

問題 No.460 裏表ちわーわ
ユーザー tnakao0123tnakao0123
提出日時 2016-12-11 21:06:51
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,996 bytes
コンパイル時間 1,900 ms
コンパイル使用メモリ 98,468 KB
実行使用メモリ 181,224 KB
最終ジャッジ日時 2024-11-29 04:00:04
合計ジャッジ時間 53,055 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,640 KB
testcase_01 AC 124 ms
157,092 KB
testcase_02 AC 4 ms
13,632 KB
testcase_03 WA -
testcase_04 AC 2 ms
13,632 KB
testcase_05 TLE -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 AC 3 ms
13,632 KB
testcase_09 AC 2 ms
157,440 KB
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 AC 3 ms
6,816 KB
testcase_25 AC 2 ms
6,820 KB
testcase_26 AC 2 ms
6,816 KB
testcase_27 AC 2 ms
154,608 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 460.cc: No.460 裏表ちわーわ - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_H = 8;
const int MAX_W = 8;
const int MAX_HW = MAX_H * MAX_W;

const int INF = 1 << 30;

const int dxs[] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dys[] = {0, -1, -1, -1, 0, 1, 1, 1};

/* typedef */

typedef unsigned long long ull;
typedef pair<ull,int> puli;
typedef map<ull,int> muli;

/* global variables */

int h, w, hw;
ull msks[MAX_HW];
muli dists;

/* subroutines */

inline int xy2p(int x, int y) { return y * w + x; }

/* main */

int main() {
  cin >> h >> w;
  hw = h * w;
  
  ull gl = 0, bi = 1;
  for (int y = 0; y < h; y++)
    for (int x = 0; x < w; x++, bi <<= 1) {
      int a;
      cin >> a;
      if (a) gl |= bi;
    }
      
  for (int y = 0, p = 0; y < h; y++)
    for (int x = 0; x < w; x++, p++) {
      msks[p] = (1ULL << p);
      for (int di = 0; di < 8; di++) {
	int x0 = x + dxs[di], y0 = y + dys[di];
	if (x0 >= 0 && x0 < w && y0 >= 0 && y0 < h)
	  msks[p] |= (1ULL << xy2p(x0, y0));
      }
    }

  queue<puli> q;
  dists[0] = 1; q.push(puli(0, 1));
  dists[gl] = -1; q.push(puli(gl, -1));

  while (! q.empty()) {
    puli u = q.front(); q.pop();
    ull &ui = u.first;
    int &ud = u.second, vd = (ud >= 0) ? ud + 1 : ud - 1;

    for (int i = 0; i < hw; i++) {
      ull vi = ui ^ msks[i];
      muli::iterator mit = dists.find(vi);
      if (mit == dists.end()) {
	dists[vi] = vd;
	q.push(puli(vi, vd));
      }
      else if ((vd >= 0 && mit->second < 0) || (vd < 0 && mit->second >= 0)) {
	int d = abs(vd - mit->second) - 2;
	printf("%d\n", d);
	return 0;
      }
    }
  }

  puts("Impossible");
  return 0;
}
0