深さ優先探索（4題）

「プログラミングコンテストチャレンジブック」第２版（マイナビ）の章末で紹介されている練習問題を解いて競技プログラミングの練習をしている。

今回は「深さ優先探索」（p.125）を4題。

深さ優先探索が使える問題の特徴は、
1. 片っ端から全探索してもあまり多くならない
2. 深さも最大で10くらいで深くなりすぎない
3. メモ化しなくても十分速く解ける
っていう感じ。
要するにあまり工夫しなくても全探索すれば解けそうな問題に使える。

POJ 1979:Red and Black

問題

#include <iostream>
using namespace std;

const int MAX_W = 20;
int w,h,cnt,sx,sy;
char tiles[MAX_W + 2][MAX_W + 2];

// 現在位置x,y
void dfs(int x, int y) {
  if (tiles[y][x] == '#') {
    return;
  }

  tiles[y][x] = '#';
  cnt++;

  dfs(x + 1, y);
  dfs(x - 1, y);
  dfs(x, y + 1);
  dfs(x, y - 1);
}

int main() {
  while(true) {
    // 入力
    cnt = 0;
    cin >> w >> h;
    if (w == 0) {
      break;
    }

    // 処理しやすくするためにタイルの周辺は'#'で埋める
    for (int i = 1; i <= h; i++) {
      tiles[i][0] = '#';
      tiles[i][w+1] = '#';
      for (int j = 1; j <= w; j++) {
        cin >> tiles[i][j];
        if (tiles[i][j] == '@') {
          sx = j;
          sy = i;
        }
      }
    }
    for (int i = 0; i <= w+1; i++) {
      tiles[0][i] = '#';
      tiles[h+1][i] = '#';
    }

    dfs(sx,sy);

    // 出力
    cout << cnt << "\n";
  }
}

POJ 3009:Curling 2.0

問題

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_W = 20;
const int MAX_CNT = 10;
int w,h,sx,sy,gx,gy;
int board[MAX_W][MAX_W];
int four_direction[4][2] = {
    {1,0}, {-1,0}, {0,1}, {0,-1}
};


// ボードの外に出ているかどうか
bool isOutOfBoard(int x, int y) {
  return x < 0 || x >= w || y < 0 || y >= h;
}

//指定した方向の隣接ブロックを壊す
void breakBlock(int x, int y, int dx, int dy) {
  if (!isOutOfBoard(x + dx, y + dy) && board[y][x] != 3)
    board[y + dy][x + dx] = 0;
}

// 指定した方向の隣接ブロックを置き直す
void restoreBlock(int x, int y, int dx, int dy) {
  if (!isOutOfBoard(x + dx, y + dy) && board[y][x] != 3)
    board[y + dy][x + dx] = 1;
}


// 指定した方向に移動する。ブロックにぶつかるか外に出るまで
pair<int,int> moveTo(int x, int y, int dx, int dy) {
  int nx = x;
  int ny = y;
  while (!isOutOfBoard(nx, ny) &&
          (isOutOfBoard(nx + dx, ny + dy) || board[ny + dy][nx + dx] != 1) &&
          board[ny][nx] != 3) {
    nx += dx;
    ny += dy;
  }
  return pair<int,int>(nx, ny);
}

// 現在位置x,y
int dfs(int x, int y, int cnt) {
  // 現在位置がゴールだったら
  if (x == gx && y == gy)
    return cnt;
  // 10回投げ終わったら
  if (cnt == 10)
    return -1;

  int res = 100;
  pair<int, int> nxny;
  int nx, ny, dx, dy;
  // 4方向に移動させ、ブロックも壊す
  for (int i = 0; i < 4; i++) {
    dx = four_direction[i][0];
    dy = four_direction[i][1];
    if (isOutOfBoard(x + dx, y + dy) || board[y + dy][x + dx] == 1)
      continue;
    nxny = moveTo(x, y, dx, dy);
    nx = nxny.first;
    ny = nxny.second;
    if (!isOutOfBoard(nx, ny)) {
      breakBlock(nx, ny, dx, dy);
      int _res = dfs(nx, ny, cnt + 1);
      if (_res > 0)
        res = min(res, _res);
      restoreBlock(nx, ny, dx, dy);
    }
  }

  return (res == 100) ? -1 : res;
}



int main() {
  while(true) {
    // 入力
    cin >> w >> h;
    if (!(w | h))
      break;
    // ボードを0で埋める
    for (int i = 0; i < MAX_W; i++) {
      for (int j = 0; j < MAX_W; j++) {
        board[i][j] = 0;
      }
    }
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        cin >> board[i][j];
        if (board[i][j] == 2) {
          sx = j;
          sy = i;
        } else if (board[i][j] == 3) {
          gx = j;
          gy = i;
        }
      }
    }

    // 深さ優先探索
    int res = dfs(sx, sy, 0);

    // 出力
    cout << res << endl;
  }
  return 0;
}

AOJ 0118:Property Distribution

問題

using namespace std;

const int MAX_W = 100;
int h,w;
char orchard[MAX_W][MAX_W];
bool counted[MAX_W][MAX_W];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void dfs(int i, int j, char tree) {
  // 今いるところが果樹園の外か、treeでないならreturn
  if (i < 0 || i >= h || j < 0 || j >= w || counted[i][j] || tree != orchard[i][j])
    return;
  // 今いる場所のcountedをtrueにする
  counted[i][j] = true;

  // 4方向に進む
  for (int k = 0; k < 4; k++) {
    dfs(i + dy[k], j + dx[k], tree);
  }
}

int main() {
  while (true) {
    // 入力
    cin >> h >> w;
    if (!(h | w))
      break;
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        cin >> orchard[i][j];
        counted[i][j] = false;
      }
    }
    // 計算
    int res = 0;
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        if (!counted[i][j]) {
          char tree = orchard[i][j];
          dfs(i, j, tree);
          res++;
        }
      }
    }

    // 出力
    cout << res << endl;
  }
}

AOJ 0033:Ball

問題

#include <iostream>
#include <vector>
using namespace std;

int a[10];
vector<int> b,c;

bool dfs(int i) {
  if (i == 10) {
    // 判定
    for (int j = 1; j < b.size(); j++) {
      if (b[j] < b[j-1])
        return false;
    }
    for (int j = 1; j < c.size(); j++) {
      if (c[j] < c[j-1])
        return false;
    }
    return true;
  }

  bool res = false;

  b.push_back(a[i]);
  res = res || dfs(i+1);
  b.pop_back();
  c.push_back(a[i]);
  res = res || dfs(i+1);
  c.pop_back();

  return res;
}

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    // 入力
    for (int j = 0; j < 10; j++) {
      cin >> a[j];
    }
    b.clear();
    c.clear();
    // 計算
    bool res = dfs(0);
    // 出力
    cout << ((res) ? "YES" : "NO")<< endl;
  }
}