Hatena::Grouptopcoder

Wrong Answer -- japlj このページをアンテナに追加 RSSフィード

 | 

2012-05-08

AOJ 1303 Hobby on Rails

| 16:23 | AOJ 1303 Hobby on Rails - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - AOJ 1303 Hobby on Rails - Wrong Answer -- japlj AOJ 1303 Hobby on Rails - Wrong Answer -- japlj のブックマークコメント

5限が始まってしまうのでソースだけ載せておこう

詳細はあとで

実装 66 分 + デバッグ 18 分

バグが少ないのは非常によろしい。丁寧に書いたので実装に時間はかかっているが、同じ程度の丁寧さでもっと速く書きたいところですね。

AC


#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int w, h;

inline int left(int d) { return (d+3)&3; }
inline int rev(int d) { return (d+2)&3; }
inline int right(int d) { return (d+1)&3; }

static int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
char type[8][8];
int dir[8][8], id[8][8], lrx[8], lry[8], done[8], lrs, sol;

int v_time[8][8][2][1<<6], v_phase[8][8][2][1<<6];

void dfs(int y, int x, int from, int st, int phase, int t)
{
  int& vp = v_phase[y][x][from][st], &vt = v_time[y][x][from][st];
  if(phase == vp) {
    sol = max(sol, t - vt);
    return;
  }
  vp = phase; vt = t;

  int ny, nx, nf, ns;
  if(type[y][x] == 'S') {
    int f = from == 0 ? dir[y][x] : rev(dir[y][x]);
    ny = y+dy[rev(f)]; nx = x+dx[rev(f)];
    nf = f; ns = st;
  } else if(type[y][x] == 'C') {
    int nd = from == 0 ? right(dir[y][x]) : dir[y][x];
    ny = y+dy[nd]; nx = x+dx[nd]; nf = rev(nd); ns = st;
  } else if(from == 1) {
    ny = y+dy[dir[y][x]]; nx = x+dx[dir[y][x]];
    nf = rev(dir[y][x]); ns = st;
  } else if(!(st & (1<<id[y][x]))) {
    ny = y+dy[rev(dir[y][x])]; nx = x+dx[rev(dir[y][x])];
    nf = dir[y][x]; ns = st ^ (1<<id[y][x]);
  } else {
    int nd = type[y][x] == 'L' ? right(dir[y][x]) : left(dir[y][x]);
    ny = y+dy[nd]; nx = x+dx[nd]; nf = rev(nd); ns = st ^ (1<<id[y][x]);
  }
  dfs(ny, nx, (dir[ny][nx] == nf ? 0 : 1), ns, phase, t+1);
}

void longest_cycle()
{
  int phase = 1;
  memset(v_phase, 0, sizeof(v_phase));
  for(int i=0; i<lrs; ++i)
    for(int j=0; j<(1<<lrs); ++j)
      for(int k=0; k<2; ++k)
	if(v_phase[lry[i]][lrx[i]][k][j] == 0)
	  dfs(lry[i], lrx[i], k, j, phase++, 0);
}

void adjust(int y, int x, int from, int cur, bool islr)
{
  if(cur == lrs) {
    longest_cycle();
    return;
  }

  if(x < 1 || y < 1 || x > w || y > h) return;

  if(islr) {
    if(cur < 0 || done[cur] == 3) { cur++; y=lry[cur]; x=lrx[cur]; }
    int d = (dir[y][x] + done[cur] * (type[y][x] == 'L' ? 1 : 3)) & 3;
    done[cur]++;
    adjust(y+dy[d], x+dx[d], rev(d), cur, false);
    done[cur]--;
    return;
  }

  if(dir[y][x] >= 0) {
    bool ok = false;
    ok |= (type[y][x] == 'S' && (dir[y][x] == from || dir[y][x] == rev(from)));
    ok |= (type[y][x] == 'C' && (dir[y][x] == from || right(dir[y][x]) == from));
    ok |= (type[y][x] == 'L' && (dir[y][x] != right(from)));
    ok |= (type[y][x] == 'R' && (right(dir[y][x]) != from));
    if(ok) adjust(lry[cur], lrx[cur], -1, cur, true);
    return;
  }

  if(type[y][x] == 'S') {
    dir[y][x] = from;
    adjust(y+dy[rev(from)], x+dx[rev(from)], from, cur, false);
  } else if(type[y][x] == 'C') {
    dir[y][x] = from;
    adjust(y+dy[right(from)], x+dx[right(from)], rev(right(from)), cur, false);
    dir[y][x] = left(from);
    adjust(y+dy[left(from)], x+dx[left(from)], rev(left(from)), cur, false);
  }
  dir[y][x] = -1;
}

int main()
{
  while(scanf("%d%d", &w, &h), w||h) {
    lrs = 0;
    for(int i=1; i<=h; ++i) {
      for(int j=1; j<=w; ++j) {
	char s[2];
	scanf("%s", s);
	type[i][j] = s[0];
	if(s[0] == 'L' || s[0] == 'R') {
	  id[i][j] = lrs;
	  lrx[lrs] = j;
	  lry[lrs] = i;
	  lrs++;
	}
      }
    }
    sol = 0;
    for(int i=0; i<(1<<(2*lrs)); ++i) {
      memset(dir, ~0, sizeof(dir));
      for(int j=0; j<lrs; ++j)
	dir[lry[j]][lrx[j]] = (i >> (2*j)) & 3;
      adjust(lry[0], lrx[0], -1, -1, true);
    }
    printf("%d\n", sol);
  }
  return 0;
}

WilsonWilson2012/11/14 15:53You have the monopoly on useful information-aren't moonpolies illegal? ;)

hrtwwfvhrtwwfv2012/11/15 12:011Bypab <a href="http://scqhjknjqoym.com/">scqhjknjqoym</a>

wdqqopcemwdqqopcem2012/11/16 10:23c8dNAR , [url=http://jutpppbbftxg.com/]jutpppbbftxg[/url], [link=http://okunxvklhmfs.com/]okunxvklhmfs[/link], http://utxxwfjihqfd.com/

pwmmnujjpwmmnujj2012/11/17 00:47iY2ahP <a href="http://pkmemxmongbs.com/">pkmemxmongbs</a>

wnulqxkqewnulqxkqe2012/11/17 20:42v1tgdp , [url=http://hxhhmnpqrrcp.com/]hxhhmnpqrrcp[/url], [link=http://knfmmbzzoqyi.com/]knfmmbzzoqyi[/link], http://watnafbfzjkt.com/

BainogarcicugBainogarcicug2014/01/21 07:41<a href="http://freecialiscialissaleyce.com/#sggo">cialis sale</a> at any time.,Some Internet pharmacies are reputable places to <a href="http://freecialiscialissalestrh.com/#nnlq">cialis dosage</a> to manage symptoms Ensure you maximize the discounts in,Cheap prices for <a href="http://cialisukcialissoftarry.com/#znua">cheap cialis</a>

nxxixydwspnxxixydwsp2014/04/02 18:51hsxlwupqdpefs, http://www.zdaaxxjata.com/ fsnsyuvbhv

vvteuyuwcgvvteuyuwcg2014/04/05 01:07ngcjeupqdpefs, <a href="http://www.yubepoaowx.com/">hzlhfetbmw</a>

ffklmljtgeffklmljtge2014/04/07 08:59kalwoupqdpefs, <a href="http://www.npbochaagt.com/">tmpbtlbjhi</a>

dlzafjelhldlzafjelhl2014/04/10 18:32idosiupqdpefs, http://www.fkpfnlnzmg.com/ dcqastnhxy

linmugxzaclinmugxzac2014/04/12 16:56xcqkwupqdpefs, <a href="http://www.fczmxgrjcn.com/">rttslmpjzj</a> , [url=http://www.lkjzhvsbdx.com/]nqtmwtgefu[/url], http://www.naartkryxa.com/ rttslmpjzj

 |