土下座しながら探索中

主に競技プログラミング

AOJ 1243 : Weather Forecast

問題リンク:Weather Forecast | Aizu Online Judge

問題概要:

解法:
メモ化再帰をした
今何日かと今どこかと1,3,9,11を最後に雨を降らしてから何日訪れていないかを記録した

初期化で毎回365*9*7*7*7*7してたらTLEをくらってしまった

コード:

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define MAX 366

using namespace std;

int dx[] = {+0,+1,+0,-1,+0,+2,+0,-2,+0};
int dy[] = {+1,+0,-1,+0,+2,+0,-2,+0,+0};
int n;
int fest[MAX];
bool visited[MAX][9][7][7][7][7];

bool isValid(int day,int cur)
{
  if((fest[day]>>cur) & 1)return false;
  if((fest[day]>>(cur+1)) & 1)return false;
  if((fest[day]>>(cur+4)) & 1)return false;
  if((fest[day]>>(cur+5)) & 1)return false;
  return true;
}

bool dfs(int day,int cur,int _1,int _3,int _9,int _11)
{

  if(visited[day][cur-(1*(cur/4))][_1][_3][_9][_11])return false;
  visited[day][cur-(1*(cur/4))][_1][_3][_9][_11] = true;

  if(!isValid(day,cur))
    {
      return false;
    }  

  if(day >= n-1)
    {
      return true;
    }

  int x = cur % 4;
  int y = cur / 4;

  rep(i,9)
    {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(!(0 <= nx && nx <= 2 && 0 <= ny && ny <= 2))continue;
      int next = nx + ny * 4;
      int cost1 = _1+1;
      int cost3 = _3+1;
      int cost9 = _9+1;
      int cost11 = _11+1;
      if(next == 0)cost1 = 0;
      if(next == 2)cost3 = 0;
      if(next == 8)cost9 = 0;
      if(next == 10)cost11 = 0;
      if(cost1 >= 7 || cost3 >= 7 || cost9 >= 7 || cost11 >= 7)continue;

      if(dfs(day+1,next,cost1,cost3,cost9,cost11))
	{
	  return true;
	}
    }
  return false;
}

int main()
{
  while(scanf("%d",&n),n)
    {
      rep(i,n)
	{
	  fest[i] = 0;
	  int schedule;
	  rep(j,16)
	    {
	      scanf("%d",&schedule);
	      if(schedule)
		{
		  fest[i] |= (1<<j);
		}
	    }
	}

      rep(i,n+1)rep(j,9)rep(k,7)rep(l,7)rep(m,7)rep(o,7)
	visited[i][j][k][l][m][o] = false;

      cout << dfs(0,5,1,1,1,1) << endl;

    }
  return 0;
}