Submission #486929


Source Code Expand

/*
 * e.cc: E: 
 */

#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 = 30;
const int MAX_W = 30;
const int DN = 8;
const int DBITS = 1 << DN;
const int DMASK = DBITS - 1;

const int INF = 1 << 30;

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

/* typedef */

struct Stat {
  int x, y, bits, d;
  Stat() {}
  Stat(int _x, int _y, int _bits, int _d): x(_x), y(_y), bits(_bits), d(_d) {}
};

/* global variables */

int flds[MAX_H][MAX_W];
int dists[MAX_H][MAX_W][DBITS];
Stat prvs[MAX_H][MAX_W][DBITS];
int pds[DN];

/* subroutines */

/* main */

int main() {
  int h, w;
  cin >> h >> w;

  memset(flds, 0, sizeof(flds));
  int sx, sy, gx, gy;
  
  for (int y = 0; y < h; y++) {
    string line;
    cin >> line;
    for (int x = 0; x < w; x++) {
      if (line[x] == '#')
	flds[y][x] = -1;
      else if (line[x] == '^')
	sx = x, sy = y;
      else if (line[x] == '$')
	gx = x, gy = y;
      else if (line[x] >= 'a' && line[x] <= 'h')
	flds[y][x] = line[x] - 'a' + 1;
      else if (line[x] >= 'A' && line[x] <= 'H')
	flds[y][x] = line[x] - 'A' + 1 + DN;
    }
  }

  for (int y = 0; y < h; y++)
    for (int x = 0; x < w; x++)
      for (int bits = 0; bits < DBITS; bits++)
	dists[y][x][bits] = INF;
  dists[sy][sx][0] = 0;
  prvs[sy][sx][0] = Stat(sx, sy, 0, -1);
  
  queue<Stat> q;
  q.push(Stat(sx, sy, 0, 0));
  int gbits = -1;
  
  while (! q.empty()) {
    Stat u = q.front(); q.pop();
    if (dists[u.y][u.x][u.bits] != u.d) continue;
    if (u.x == gx && u.y == gy) {
      gbits = u.bits;
      break;
    }

    int vd = u.d + 1;
    
    for (int di = 0; di < 4; di++) {
      int vx = u.x + dxs[di], vy = u.y + dys[di];
      if (vx >= 0 && vx < w && vy >= 0 && vy < h && flds[vy][vx] >= 0) {
	int vbits = u.bits, vf = flds[vy][vx];
	if (vf >= 1 && vf <= DN)
	  vbits |= 1 << (vf - 1);
	else if (vf > DN && ! (vbits & (1 << (vf - DN - 1)))) continue;

	if (dists[vy][vx][vbits] > vd) {
	  dists[vy][vx][vbits] = vd;
	  q.push(Stat(vx, vy, vbits, vd));
	  prvs[vy][vx][vbits] = u;
	}
      }
    }
  }

  if (dists[gy][gx][gbits] >= INF) {
    cout << -1 << endl;
    return 0;
  }
  
  int mt = 0;
  memset(pds, 0, sizeof(pds));

  for (int y = gy, x = gx, bits = gbits; prvs[y][x][bits].d > 0;) {
    Stat u = prvs[y][x][bits];
    int uf = flds[u.y][u.x];
    if (uf >= 1 && uf <= DN) {
      int k = uf - 1;
      if (pds[k] > 0) {
	mt += pds[k] - u.d;
	for (int i = 0; i < DN; i++)
	  if (pds[i]) mt++;
	pds[k] = 0;
      }
    }
    else if (uf > DN) {
      int k = uf - DN - 1;
      if (pds[k] == 0) pds[k] = u.d;
    }

    x = u.x, y = u.y, bits = u.bits;
  }
  
  cout << (dists[gy][gx][gbits] + mt) << endl;

  return 0;
}

Submission Info

Submission Time
Task E - Magic Doors
User tnakao
Language C++ (GCC 4.4.7)
Score 0
Code Size 3127 Byte
Status WA
Exec Time 44 ms
Memory 5544 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 13
WA × 7
Set Name Test Cases
All 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 3, 4, 5, 6, 7, 8, 9
Case Name Status Exec Time Memory
1 AC 33 ms 1048 KB
10 WA 30 ms 1172 KB
11 AC 44 ms 5544 KB
12 AC 36 ms 4012 KB
13 AC 33 ms 1324 KB
14 AC 32 ms 1484 KB
15 AC 32 ms 1356 KB
16 AC 35 ms 3092 KB
17 WA 35 ms 2632 KB
18 WA 37 ms 4496 KB
19 WA 37 ms 5264 KB
2 AC 30 ms 1116 KB
20 WA 30 ms 2000 KB
3 AC 29 ms 984 KB
4 AC 29 ms 1104 KB
5 WA 29 ms 1100 KB
6 AC 29 ms 1100 KB
7 WA 29 ms 1096 KB
8 AC 29 ms 1100 KB
9 AC 30 ms 1160 KB