SRM 706 Div1

寝ながら出た.

Easy を解けて 87th. 1522 -> 1635(+113). 直近 2 回で計 +323 してて面白い.

Easy (250) MovingCandies

TopCoder Statistics - Problem Statement

問題概要

'#' か '.' からなる の 次元グリッドが与えられる. '#' をいくつか動かすことにより, から に 辺で隣接する '#' だけを通って移動できるようにする.

移動する '#' の最小個数を求めよ. 移動できないとき -1.

解法

一瞬何も浮かばずにフローか？(適当) となったので, また 0 完と思ったけど冷静に考えれば簡単.

BFS でえいってする方針で, 状態を

cost[x][y][今までに通った '#' の個数] := 今までに通った '.' の最小個数

とすれば, を満たす で, cost[W][H][ ] がグリッド全体の '#' の個数以下のもののうち(より大きいと '#' が足りない), cost[W][H][ ] の最小値 となる.

ソース

コストが 0 か 1 なので 0-1BFS で良いんだけど, よくわからなくて Dijkstra でやっているので log がついて となってます...

#include <bits/stdc++.h>
using namespace std;
 
const int INF = 1 << 30;
typedef tuple< int, int, int, int > Pi;
const int dy[] = {0, 1, 0, -1}, dx[] = {1, 0, -1, 0};
 
class MovingCandies
{
public:
  int minMoved(vector <string> t)
  {
    priority_queue< Pi, vector< Pi >, greater< Pi > > que;
    int cost[20][20][405];
    fill_n(**cost, 20 * 20 * 405, INF);
    int ff = t[0][0] == '.';
    que.emplace(ff, 0, 0, !ff);
    cost[0][0][!ff] = ff;
    while(!que.empty()) {
      int c, x, y, vv;
      tie(c, x, y, vv) = que.top();
      que.pop();
      if(vv == 401) continue;
      if(cost[x][y][vv] < c) continue;
      for(int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx < 0 || ny < 0 || nx >= t[0].size() || ny >= t.size()) continue;
        int nc = c + (t[ny][nx] == '.');
        int nv = vv + (t[ny][nx] == '#');
        if(cost[nx][ny][nv] <= nc) continue;
        cost[nx][ny][nv] = nc;
        que.emplace(nc, nx, ny, nv);
      }
    }
    int ret = INF;
    for(int i = 0; i <= 401; i++) {
      int sharp = i;
      int last = cost[t[0].size() - 1][t.size() - 1][i];
      if(sharp + last <= all) ret = min(ret, last);
    }
    if(ret == INF) return(-1);
    return(ret);
  }
};