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

Tamflexの貯蔵庫

やる気のない備忘録

codeIQ 2791

codeiq.jp

例によってdfsとメモ再帰で解けます.

struct P
{
  int x;
  int y;
  P(){};
  P(int x,int y):x(x),y(y){};
  P operator+(const P&q){P t;t.x=x+q.x;t.y=y+q.y;return t;}
  P operator+=(const P&q){x+=q.x;y+=q.y;return *this;}
  bool operator!=(const P&q){return (x!=q.x)||(y!=q.y);}
  bool operator==(const P&q){return (x==q.x)&&(y==q.y);}
};

int n;
vector<vector<int> > a;
int dp[100][100][4];
int visited[100][100][4];
vector<P> dir;

int dx[] = {1,0,-1,0};
int dy[] = {0,-1,0,1};

bool out(P p)
{
  if(p.x < 0 || p.y < 0 || p.x >= n || p.y >= n) return true;
  else return a[p.x][p.y] == 0;
}

int dfs(P s, P g, int d, int cnt)
{
  int ps = s.x*n+s.y;
  int pg = g.x*n+g.y;
  if(dp[ps][pg][d]!=-1) return dp[ps][pg][d];
  if(visited[ps][pg][d]) return INF;
  visited[ps][pg][d] = true;
  if(cnt > 1000) return INF;
  P p = s;
  while(!out(p+dir[d]))
  {
    p+=dir[d];
    if(p==g) return 0;
  }
  int pp = p.x*n+p.y;
  int p1 = dfs(p,g,(d+1)%4,cnt+1);
  int p2 = dfs(p,g,(d+3)%4,cnt+1);
  dp[pp][pg][(d+1)%4] = p1;
  dp[pp][pg][(d+3)%4] = p2;
  return min(p1,p2)+1;
}

int solve(P s, P g)
{
  int ans = INF;
  REP(i,4)
  {
    memset(dp,-1,sizeof(dp));
    memset(visited,0,sizeof(visited));
    ans = min(ans,dfs(s,g,i,0));
  }
  return ans;
}

int main()
{
  cin >> n;
  a.resize(n);
  REP(i,n)
  {
    a[i].resize(n);
    string s; cin >> s;
    REP(j,n) if(s[j]=='O') a[i][j] = 1;
  }
  REP(i,4) dir.push_back(P(dx[i],dy[i]));
  int ans = 0;
  REP(i,n) REP(j,n) if(a[i][j])
  {
    for(int k=i*n+j+1;k<n*n;k++) if(a[k/n][k%n])
    {
      int tmp = solve(P(i,j),P(k/n,k%n));
      if(tmp != INF) ans = max(ans,tmp);
    }
  }
  cout << ans << endl;
  return 0;
}