読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

aoj 0091

にじみ | Aizu Online Judge
dfsを使うところまでは良かったが探索の仕方がまずかった.
まず最初に試したのは全ての探索木の節/葉において全部(8*8)を探索する方法でこれだとTLEしてしまった.
自力では解けなかったので先人達の答えを拝見させていただいた.
調べた結果以下のようなアルゴリズムが見つかった.
(i,j)について左上から右下へ探索し…(配列で扱いやすくするため問題分のx,yとi,jは逆にしている)

  1. (i+1,j)から小を吸い取る
  2. (i+1,j+1)から中を吸い取る
  3. (i+2,j+2)から大を吸い取る
  4. 上3つのパターンが不可能ならばfalse <- ここ重要

これによって判定及び枝刈りが高速に行えるので当初のやり方よりも早くできる
計算量の見積は当初のアルゴリズムが最悪O(100^n)なのに対してこのアルゴリズムだとO(3^n)程度でいけそう?

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

int n;
int a[10][10];
int di[] = {0,1,1,2};
int dj[] = {0,0,1,0};

bool canPos(int i, int j, int t)
{
  switch(t)
  {
    case 3:
      if(i<=1||i>=8||j<=1||j>=8) return false;
      FOR(k,-2,2) FOR(l,-(2-abs(k)),(2-abs(k))) if(a[i+k][j+l]==0) return false;
      return true;
    case 2:
      if(i<=0||i>=9||j<=0||j>=9) return false;
      FOR(k,-1,1) FOR(l,-1,1) if(a[i+k][j+l]==0) return false;
      return true;
    case 1:
      if(i<=0||i>=9||j<=0||j>=9) return false;
      FOR(k,-1,1) FOR(l,-(1-abs(k)),1-abs(k)) if(a[i+k][j+l]==0) return false;
      return true;
    default:
      return false;
  }
}

void turn(int i, int j, int t, int c)
{
  switch(t)
  {
    case 3:
      FOR(k,-2,2) FOR(l,-(2-abs(k)),(2-abs(k))) a[i+k][j+l]+=c;
      break;
    case 2:
      FOR(k,-1,1) FOR(l,-1,1) a[i+k][j+l]+=c;
      break;
    case 1:
      FOR(k,-1,1) FOR(l,-(1-abs(k)),1-abs(k)) a[i+k][j+l]+=c;
    default:
      break;
  }
}

bool dfs(int n)
{
  if(n==0)
  {
    REP(i,10) REP(j,10) if(a[i][j] > 0) return false;
    return true;
  }
  REP(i,10) REP(j,10) if(a[i][j])
  {
    int x, y;
    FOR(t,1,3) if(canPos(y=i+di[t],x=j+dj[t],t))
    {
      turn(y,x,t,-1);
      if(dfs(n-1)) {printf("%d %d %d\n",x,y,t); return true;}
      turn(y,x,t,1);
    }
    return false;
  }
  return false;
}

int main()
{
  cin >> n;
  REP(i,10) REP(j,10) cin >> a[i][j];
  dfs(n);
  return 0;
}