377A : Maze

問題リンク：Problem - 377A - Codeforces

問題概要：
n*mの迷路があたえられる
迷路は'.'または'#'からなる
'.'はそのセルが空であることを示す
'#'はそのセルが壁であることを示す
自分は空のセルにk個だけ壁を追加する
壁を追加したあと、空のセルのエリアは連結でなければならない
この条件を満たすような壁の追加のしかたを求めよ
必ず答えは存在する
初期状態では空のセルのエリアは連結である

解法：
空のセルのエリアからDFS or BFSで(空のセルの数-k)個の連続なエリアを求める
そこで求めたエリア以外の場所に壁を追加すればよい

最近使い始めたC++11のlambda関数が使いたいがためにわざわざBFSで書いた
おかげで１WAだしてしまったわけだが。。。言い訳か

コード：

#include<iostream>
#include<tuple>
#include<algorithm>
#include<deque>
#include<vector>
#include<cassert>
#include<climits>

#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 510

using namespace std;

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int h,w,k,empty_cell,sp;
char G[MAX][MAX];
bool used[MAX][MAX];

int main(){
  sp = IINF;
  cin >> h >> w >> k;
  rep(i,h)rep(j,w){
    cin >> G[i][j];
    if(G[i][j]=='.'){
      empty_cell++;
      if(sp == IINF)sp = j + i * w;
    }
  }

  auto isValid = [](int x,int y){ return ( 0 <= x && x < w && 0 <= y && y < h ); };

  int remain = empty_cell - k;
  assert(remain >= 0);
  deque<int> deq;
  deq.push_back(sp);
  while(!deq.empty() && remain){
    int cur = deq.front(); deq.pop_front();
    if(used[cur/w][cur%w])continue;
    used[cur/w][cur%w] = true;
    remain--;
    if(remain <= 0)break;

    rep(i,4){
      int nx = ( cur % w ) + dx[i];
      int ny = ( cur / w ) + dy[i];
      if(!isValid(nx,ny))continue;
      if(G[ny][nx] == '#' || used[ny][nx] )continue;
      deq.push_back(nx+ny*w);
    }

  }

  rep(y,h){
    rep(x,w){
      if(!used[y][x] && G[y][x] == '.')cout << 'X';
      else          cout << G[y][x];
    }
    cout << endl;
  }

  return 0;
}