google code jam 2010 Round 1A Rotate

program

問題

http://code.google.com/codejam/contest/dashboard?c=544101#

  • 縦横Nマスに文字R, Bが配置されている。
  • これを右に90度回転させて、各文字を「重力」で下に落とす。
  • この時、R, BがK個以上縦横斜めのいずれかの方向に並んでいるかどうかをチェックしなさい。

方針

  • ゲーム盤を回転させて各文字を「重力」で下に落とす作業は、実は、各文字を右にずらせるだけずらすのと同じ。
  • R or BがK文字以上連なっているかどうかは、再帰で、深さ優先探索的にチェック。
    • id:chokudai さんは、メモ用の配列を用意して、DPっぽい実装でした。

回答例

/*! g++ main.cpp -DNDEBUG
 */

#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <iterator>

using namespace std;
typedef unsigned long ul;


class Solve{
public:
  int k, n;
  vector<int> dx, dy;
  vector<vector<char> > table;
  Solve():dx(4), dy(4){
    dx[0] = 1; dy[0] = 0;
    dx[1] = 0; dy[1] = 1;
    dx[2] = 1; dy[2] = 1;
    dx[3] = -1; dy[3] = 1;
  }

  bool dfs(int i, int j, int ii, int jj, int depth, char check){
    if(i < 0 || j < 0 || i >= n || j >= n) return false;
    if(table[i][j] == check){
      if(depth == k) return true;
      if(dfs(i + ii, j + jj, ii, jj, depth + 1, check)) return true;
    }
    return false;
  }


  void solve(int t){
    string ret;

    cin >> n >> k;

    table.resize(n);
    fill(table.begin(), table.end(), vector<char>(n, '.'));

    for(int i = 0; i < n; i++){
      string buf;
      cin >> buf;
      int pos = n; 
      for(int j = n - 1; j >= 0; j--){
	if(buf[j] != '.'){
	  table[i][--pos] = buf[j];
	}
      }
    }

    bool red_win  = false;
    bool blue_win = false;
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
	for(int x = 0; x < 4; x++){
	  blue_win = blue_win || dfs(i, j, dx[x], dy[x], 1, 'B');
	  red_win  = red_win  || dfs(i, j, dx[x], dy[x], 1, 'R');
	}
      }
    }

    if(red_win && blue_win)
      ret = "Both";
    else if(red_win)
      ret = "Red";
    else if(blue_win)
      ret = "Blue";
    else
      ret = "Neither";

    cout << "Case #" << t << ": " << ret << endl;
  }
};

int main(int argc, char* argv){

  int num_case;
  cin >> num_case;

  for(int i = 0; i < num_case; i++){
    Solve s;
    s.solve(i + 1);
  }

  return 0;
}