Japan Alumni Group Summer Camp 2013 Warming Up

Submission #487222

Source codeソースコード

/*
 * 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) {}
  bool operator>(const Stat& s) const { return d > s.d; }
  void print() {printf("Stat: x=%d, y=%d, bits=%02x, d=%d\n", x, y, bits, d);}
};

/* global variables */

int flds[MAX_H][MAX_W];
int dists[MAX_H][MAX_W][DBITS], ds0[MAX_H][MAX_W][DBITS];
Stat prvs[MAX_H][MAX_W][DBITS];
int bnums[DBITS];

/* subroutines */

/* main */

int main() {
  for (int bits = 0; bits < DBITS; bits++) {
    bnums[bits] = 0;
    for (int i = 0; i < DN; i++)
      if (bits & (1 << i)) bnums[bits]++;
  }

  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] = ds0[y][x][bits] = INF;
  dists[gy][gx][0] = ds0[gy][gx][0] = 0;
  prvs[gy][gx][0] = Stat(gx, gy, 0, -1);
  
  priority_queue<Stat,vector<Stat>,greater<Stat> > q;
  q.push(Stat(gx, gy, 0, 0));
  
  while (! q.empty()) {
    Stat u = q.top(); q.pop();
    if (dists[u.y][u.x][u.bits] != u.d) continue;
    //u.print();

    if (u.x == sx && u.y == sy && u.bits == 0) break;

    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];
	int vd = u.d + 1, vd0 = ds0[u.y][u.x][u.bits] + 1;

	if (vf > DN) {
	  int k = vf - DN - 1, bk = 1 << k;
	  vbits |= bk;
	}
	else if (vf >= 1) {
	  int k = vf - 1, bk = 1 << k;
	  if (vbits & bk) {
	    Stat pu = u;
	    while (prvs[pu.y][pu.x][pu.bits].bits & bk)
	      pu = prvs[pu.y][pu.x][pu.bits];
	    vd += vd0 - ds0[pu.y][pu.x][pu.bits] + bnums[vbits];
	    vbits &= ~bk;
	  }
	}

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

  cout << (dists[sy][sx][0] >= INF ? -1 : dists[sy][sx][0]) << endl;

  return 0;
}

Submission

Task問題 E - Magic Doors
User nameユーザ名 Nakao
Created time投稿日時
Language言語 C++ (GCC 4.4.7)
Status状態 WA
Score得点 0
Source lengthソースコード長 3205 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
All 0 / 100 1,10,11,12,13,14,15,16,17,18,19,2,20,3,4,5,6,7,8,9

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
1 AC 25 ms 808 KB
10 WA
11 AC 89 ms 6312 KB
12 AC 48 ms 4640 KB
13 AC 24 ms 1060 KB
14 AC 25 ms 1316 KB
15 AC 25 ms 1320 KB
16 AC 34 ms 3296 KB
17 WA
18 WA
19 WA
2 AC 24 ms 804 KB
20 WA
3 AC 24 ms 932 KB
4 AC 26 ms 932 KB
5 AC 25 ms 928 KB
6 AC 24 ms 804 KB
7 WA
8 AC 25 ms 924 KB
9 AC 24 ms 932 KB