結果

問題 No.460 裏表ちわーわ
コンテスト
ユーザー tnakao0123
提出日時 2016-12-11 21:06:51
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,996 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,900 ms
コンパイル使用メモリ 98,468 KB
実行使用メモリ 181,224 KB
最終ジャッジ日時 2024-11-29 04:00:04
合計ジャッジ時間 53,055 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 1 TLE * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/* -*- 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