結果

問題 No.460 裏表ちわーわ
ユーザー tnakao0123tnakao0123
提出日時 2016-12-11 21:06:51
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,996 bytes
コンパイル時間 1,510 ms
コンパイル使用メモリ 97,184 KB
実行使用メモリ 174,828 KB
最終ジャッジ日時 2023-08-19 11:35:33
合計ジャッジ時間 4,659 ms
ジャッジサーバーID
(参考情報)
judge15 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 106 ms
7,900 KB
testcase_02 AC 4 ms
4,376 KB
testcase_03 WA -
testcase_04 AC 1 ms
4,376 KB
testcase_05 TLE -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
権限があれば一括ダウンロードができます

ソースコード

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