Sun May 3 13:59:49 JST 2015

// you can this source
// also at: https://gist.github.com/cympfh/8aa0b2aa0d26b8822bed
#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define loop for(;;)
#define trace(var) cerr<<">>> "<<#var<<" = "<<var<<endl;
#define inf (1e9)
#define eps (1e-9)

// 盤の空いてるところ集合
inline
vector<int> empties(vector<int>&v) {
  vector<int> r;
  rep (i, 9) if (v[i] == 0) r.push_back(i);
  return r;
}

inline
int num_empty(vector<int>&v) {
  return empties(v).size();
}

inline
bool is_full(vector<int>&v) {
  return num_empty(v) == 0;
}

// 決着がついてるかどうか
// 0: ついてない
// ついてる場合
// 1: o (Alice) の勝ち
// 2: x (Bob) の勝ち
inline
int is_goal(vector<int>&v) {
  for (int t=1; t<3; ++t) {
    rep (k, 3) {
      if ( v[3 * k + 0] == t
       and v[3 * k + 1] == t
       and v[3 * k + 2] == t ) return t;
      if ( v[k + 0] == t
       and v[k + 3] == t
       and v[k + 6] == t ) return t;
    }
    if (v[0] == t
      and v[4] == t
      and v[8] == t ) return t;
    if (v[2] == t
        and v[4] == t
        and v[6] == t ) return t;
  }
  return 0;
}

// search のなかで使う探索メモ
map<vector<int>, int> memo;

// v: 盤の状態
// b: Aliceの手版であるか？の
//
// 返り値
// 0: 引き分け
// 1: Aliceの勝ち
// 2: Bobの勝ち
int search(vector<int> v, bool b) {
  if (memo.count(v) > 0) return memo[v];
  if (is_goal(v)) return memo[v] = is_goal(v);
  if (is_full(v)) return memo[v] = 0;
  auto es = empties(v);
  int t = b ? 1 : 2;
  bool drawable = false;
  for (int e: es) {
    v[e] = t;
    // 状態をDFSする
    int r = search(v, (not b));
    // それを指せば必勝なら勝ち
    if (r == t) return memo[v] = t;
    // せめて引き分けにもっていけるかどうかメモしておく
    if (r == 0) drawable = true;
    v[e] = 0;
  }
  // ここに到達するということは必勝の手は無かったということ
  if (drawable) return memo[v] = 0;
  // 引き分けにも出来ないのなら必敗
  return memo[v] = (3 - t);
}

int solve(string s) {
  vector<int> f(9); rep (i, 9) f[i] = s[i] == 's' ? 0 : s[i] == 'o' ? 1 : 2;
  bool b = num_empty(f) % 2 == 1; // is o's turn?
  return search(f, b);
}

int main() {
  string s;
  while (getline(cin, s)) {
    int res = solve(s);
    cout << ((res == 0) ? 'd' : (res == 1) ? 'o' : 'x') << endl;
  }
  return 0;
}

$ cat input
sssssssss
ssssossss
ssssossxs
$ ./a.out < input
d
d
o