チームラボ x 高専プロコン x パズル

全消しパズルの最短経路を導き出せ!

チームラボが、全消しが前提の最短経路を求めるパズルを実施。マウスやキーボード、フリックで操作して直感的に解く方法、プログラムを考えて解く方法の二種類で参加が可能。

応募資格・優勝景品

2014年時点で、高専生のみが対象。

希望者にはチームラボ選考スキップ、解答者の中から優秀な成績を収めた方1名にAR.Drone2.0プレゼント!

レッドコーダーによる回答例

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

/**
 * ビームサーチ
 * 
 * 評価関数は(消えるセル数*10000+連結or一間トビのセルペア数*2).
 * ゴールが一意に定まらないので両側探索が使えないが、ある程度ゴールが見えた場合は両側探索でもいけそう。
 * 評価関数も甘々なので改善の余地は結構ある。
 *
 */
public class Puzdra {
  static Scanner in;
  static PrintWriter out;
  static String INPUT = "5 6\r\n" +
      "0 1 2 3 4 2\n" + // club:0, spade:1, onpu:2, heart:3, daia:4, star:5
      "3 3 5 5 0 1\n" +
      "0 2 0 5 2 2\n" +
      "1 1 4 3 0 4\n" +
      "4 5 3 4 5 1";
  static final int beamWidth = 100000;
  
  static void solve()
  {
    int n = ni(), m = ni();
    int[][] map = new int[n][m];
    for(int i = 0;i < n;i++){
      for(int j = 0;j < m;j++){
        map[i][j] = ni();
      }
    }
    
    // 現在の状態
    Queue<State> pq = new PriorityQueue<State>(beamWidth+1, new Comparator<State>(){
      public int compare(State x, State y){
        if(x.score != y.score)return x.score - y.score;
        return Long.compare(x.h(), y.h());
      }
    });
    LongHashSet prevcache = new LongHashSet(); // 1手前の重複排除用のキャッシュ
    LongHashSet prev2cache = new LongHashSet(); // 2手前の重複排除用のキャッシュ
    for(int i = 0;i < n;i++){
      for(int j = 0;j < m;j++){
        State s = new State(map, i, j);
        pq.add(s);
        prevcache.add(s.h());
      }
    }
    for(int step = 0;step <= 100000;step++){ // step+1手目のシミュレート
      LongHashSet cache = new LongHashSet();
      
      // 次の状態
      Queue<State> npq = new PriorityQueue<State>(beamWidth+1, new Comparator<State>(){
        public int compare(State x, State y){
          if(x.score != y.score)return x.score - y.score;
          return Long.compare(x.h(), y.h());
        }
      });
      tr("STEP:" + step + " " + pq.size() + " " + pq.peek().score); // ビリのスコア
      for(State s : pq){
        if(s.score >= 10000*n*m){ // 全消し
          tr(s.map);
          int[] hist = s.history.toArray();
          tr("from (" + (hist[1]<<2|hist[0]) + "," + (hist[3]<<2|hist[2]) + ")");
          for(int i = 4;i < hist.length;i++){
            System.out.print("DRUL".charAt(hist[i]));
          }
          System.out.println();
          return;
        }
        for(int k = 0;k < 4;k++){
          if(s.canmove(k)){
            State ns = new State(s);
            ns.move(k);
            if(!cache.contains(ns.h()) && !prevcache.contains(ns.h()) && !prev2cache.contains(ns.h())){
//            if(!cache.contains(ns.h()) && !prevcache.contains(ns.h())){
              if(npq.size() >= beamWidth && npq.peek().score > ns.score)continue;
              npq.add(ns);
              cache.add(ns.h());
              if(npq.size() > beamWidth)npq.poll();
            }
          }
        }
      }
      pq = npq;
      prev2cache = prevcache;
      prevcache = cache;
    }
  }
  
  // 履歴格納用
  static class SL {
    long[] a; // 履歴本体
    int p = 0; // aのindex
    int w = 0; // word size 
    int b = 0; // word内のindex 
    int sz = 0; // 伸長したときの要素数
    
    public SL(SL o) {
      this.p = o.p;
      this.w = o.w;
      this.b = o.b;
      this.sz = o.sz;
      a = Arrays.copyOf(o.a, o.a.length);
    }
    public SL(int n, int w) { a = new long[n]; sz = 0; this.w = w; }
    public SL add(int n)
    {
      if(p+1 >= a.length && b+w >= 64 || p >= a.length)a = Arrays.copyOf(a, a.length*3/2+1);
      for(int i = 0;i < w;i++){
        if(n<<~i<0){
          a[p] |= 1L<<b;
        }
        if(++b >= 64){
          b -= 64;
          p++;
        }
      }
      sz++;
      return this;
    }
    public int size() { return sz; }
    public void clear() { p = 0; sz = 0; b = 0; }
    public int[] toArray() {
      int[] ret = new int[sz];
      int lp = 0, lb = 0, lsz = 0;
      while(lp < p || lp == p && lb < b){
        for(int i = 0;i < w;i++){
          if(a[lp]<<~lb<0){
            ret[lsz] |= 1<<i;
          }
          if(++lb >= 64){
            lb -= 64;
            lp++;
          }
        }
        lsz++;
      }
      return ret;
    }
  }
  
  static class State
  {
    SL history; // その状態に至る履歴
    int[] map; // 現在の状態。各行、1セルの情報は3bitずつ格納されている。
    int cr, cc; // 現在位置
    int n, m;
    int score; // スコア。300000以上で完成。
    long h; // ハッシュ
    public State(int[][] a, int cr, int cc) {
      n = a.length; m = a[0].length;
      this.cr = cr; this.cc = cc;
      map = new int[n];
      for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
          map[i] |= a[i][j]<<j*3;
        }
      }
      score = numel(map, m);
      history = new SL(2, 2);
      history.add(cr).add(cr>>>2);
      history.add(cc).add(cc>>>2);
    }
    public State(State s) {
      n = s.n; m = s.m;
      this.cr = s.cr; this.cc = s.cc;
      map = new int[n];
      for(int i = 0;i < n;i++){
        map[i] = s.map[i];
      }
      score = numel(map, m);
      
      history = new SL(s.history);
    }
    
    static final int[] dr = { 1, 0, -1, 0 };
    static final int[] dc = { 0, 1, 0, -1 };
    
    public boolean canmove(int dir)
    {
      int nr = cr + dr[dir], nc = cc + dc[dir];
      return nr >= 0 && nr < n && nc >= 0 && nc < m;
    }
    
    public State move(int dir)
    {
      int nr = cr + dr[dir], nc = cc + dc[dir];
      int y = map[nr]>>>nc*3&7;
      int x = map[cr]>>>cc*3&7;
      if(x != y){
        map[cr] ^= (x^y)<<cc*3;
        map[nr] ^= (x^y)<<nc*3;
      }
      cr = nr; cc = nc;
      history.add(dir);
      score = numel(map, m);
      return this;
    }
    
    public long h()
    {
      if(this.h != 0)return h;
      h = 0;
      for(int i =0 ;i < n;i++){
        h = h * 1000000007 + map[i];
      }
      h = h * 1000000007 + cr;
      h = h * 1000000007 + cc;
      return h;
    }
    
    @Override
    public String toString() {
      return "State [map="
          + Arrays.toString(map) + ", cr=" + cr + ", cc=" + cc
          + ", n=" + n + ", m=" + m + ", score=" + score + ", h=" + h
          + "]";
    }
  }
  
  /**
   * スコア計算
   * (3連以上並んでいるセルの個数, 隣接あるいは一間トビの同色ペアの個数)を数える
   * 
   * @param map
   * @param m マップの幅
   * @return
   */
  static int numel(int[] map, int m)
  {
    int n = map.length;
    int[] el = new int[n];
    for(int i = 0;i < n;i++){
      int ch = 0;
      for(int j = 0;j < m;j++){
        if(j > 0 && (map[i]>>>j*3&7) == (map[i]>>>(j-1)*3&7)){
          ch++;
        }else{
          if(ch >= 3){
            el[i] |= (1<<j)-(1<<j-ch);
//            for(int k = j-ch;k < j;k++){
//              el[i] |= 1<<k;
//            }
          }
          ch = 1;
        }
      }
      if(ch >= 3){
        el[i] |= (1<<m)-(1<<m-ch);
//        for(int k = m-ch;k < m;k++){
//          el[i] |= 1<<k;
//        }
      }
    }
    for(int i = 0;i < m;i++){
      int ch = 0;
      for(int j = 0;j < n;j++){
        if(j > 0 && (map[j]>>>i*3&7) == (map[j-1]>>>i*3&7)){
          ch++;
        }else{
          if(ch >= 3){
            for(int k = j-ch;k < j;k++){
              el[k] |= 1<<i;
            }
          }
          ch = 1;
        }
      }
      if(ch >= 3){
        for(int k = n-ch;k < n;k++){
          el[k] |= 1<<i;
        }
      }
    }
    int ct = 0;
    for(int i = 0;i < n;i++){
      ct += Integer.bitCount(el[i]);
    }
    if(ct == 30){
      tr(tos(map, m));
    }
    
    int subct = 0;
    for(int i = 0;i < n;i++){
      for(int j = 0;j < m;j++){
        if(i+1 < n && (map[i]>>>j*3&7) == (map[i+1]>>>j*3&7))subct += 2;
        if(j+1 < m && (map[i]>>>j*3&7) == (map[i]>>>(j+1)*3&7))subct += 2;
        if(i+2 < n && (map[i]>>>j*3&7) == (map[i+2]>>>(j)*3&7))subct += 2;
        if(j+2 < m && (map[i]>>>j*3&7) == (map[i]>>>(j+2)*3&7))subct += 2;
//        if(i+1 < n && j+1 < m && (map[i]>>>j*3&7) == (map[i+1]>>>(j+1)*3&7))subct += 1;
//        if(i+1 < n && j-1 >= 0 && (map[i]>>>j*3&7) == (map[i+1]>>>(j-1)*3&7))subct += 1;
      }
    }
    return ct*10000+subct;
  }
  
  public static class LongHashSet {
    public long[] keys;
    public boolean[] allocated;
    private int scale = 1<<2;
    private int rscale = 1<<1;
    private int mask = scale-1;
    public int size = 0;
    
    public LongHashSet(){
      allocated = new boolean[scale];
      keys = new long[scale];
    }
    
    public boolean contains(long x)
    {
      int pos = h(x)&mask;
      while(allocated[pos]){
        if(x == keys[pos])return true;
        pos = pos+1&mask;
      }
      return false;
    }
    
    public boolean add(long x)
    {
      int pos = h(x)&mask;
      while(allocated[pos]){
        if(x == keys[pos])return false;
        pos = pos+1&mask;
      }
      if(size == rscale){
        resizeAndAdd(x);
      }else{
        keys[pos] = x;
        allocated[pos] = true;
      }
      size++;
      return true;
    }
    
    public boolean remove(long x)
    {
      int pos = h(x)&mask;
      while(allocated[pos]){
        if(x == keys[pos]){
          size--;
          // take last and fill rmpos
          int last = pos;
          pos = pos+1&mask;
          while(allocated[pos]){
            int lh = h(keys[pos])&mask;
            // lh <= last < pos
            if(
                lh <= last && last < pos ||
                pos < lh && lh <= last ||
                last < pos && pos < lh
                ){
              keys[last] = keys[pos];
              last = pos;
            }
            pos = pos+1&mask;
          }
          keys[last] = 0;
          allocated[last] = false;
          
          return true;
        }
        pos = pos+1&mask;
      }
      return false;
    }
    
    private void resizeAndAdd(long x)
    {
      int nscale = scale<<1;
      int nrscale = rscale<<1;
      int nmask = nscale-1;
      boolean[] nallocated = new boolean[nscale];
      long[] nkeys = new long[nscale];
      itrreset();
      while(true){
        long y = next();
        if(end())break;
        int pos = h(y)&nmask;
        while(nallocated[pos])pos = pos+1&nmask;
        nkeys[pos] = y;
        nallocated[pos] = true;
      }
      {
        int pos = h(x)&nmask;
        while(nallocated[pos])pos = pos+1&nmask;
        nkeys[pos] = x;
        nallocated[pos] = true;
      }
      allocated = nallocated;
      keys = nkeys;
      scale = nscale;
      rscale = nrscale;
      mask = nmask;
    }
    
    public int itr = -1;
    
    public void itrreset() { itr = -1; }
    public boolean end() { return itr == -1; }
    
    private static long NG = Long.MIN_VALUE;
    public long next() {
      while(++itr < scale && !allocated[itr]);
      if(itr == scale){
        itr = -1;
        return NG;
      }
      return keys[itr];
    }
    
//    public int h(int x)
//    {
//      x ^= x>>>16;
//      x *= 0x85ebca6b;
//      x ^= x>>>13;
//      x *= 0xc2b2ae35;
//      x ^= x>>>16;
//      return (int)x;
//    }
    
    private int h(long x)
    {
      x ^= x>>>33;
      x *= 0xff51afd7ed558ccdL;
      x ^= x>>>33;
      x *= 0xc4ceb9fe1a85ec53L;
      x ^= x>>>33;
      return (int)(x^(x>>>32));
    }
    
    @Override
    public String toString()
    {
      itrreset();
      long[] vals = new long[size];
      int p = 0;
      while(true){
        long y = next();
        if(end())break;
        vals[p++] = y;
      }
      return Arrays.toString(vals);
    }
  }
  
  /**
   * mapの図示
   * @param b
   * @param m
   * @return
   */
  static String tos(int[] b, int m)
  {
    StringBuilder sb = new StringBuilder();
    for(int row : b){
      for(int j = 0;j < m;j++){
        sb.append(row>>>3*j&7);
      }
      sb.append("\n");
    }
    return sb.toString();
  }
  
  public static void main(String[] args) throws Exception
  {
    in = INPUT.isEmpty() ? new Scanner(System.in) : new Scanner(INPUT);
    out = new PrintWriter(System.out);
    
    long S = System.nanoTime();
    solve();
    long G = System.nanoTime();
    tr((G-S)/1000000 + "ms");
    out.flush();
  }
  
  static int ni() { return Integer.parseInt(in.next()); }
  static long nl() { return Long.parseLong(in.next()); }
  static double nd() { return Double.parseDouble(in.next()); }
  static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
          

GitHubで見る