Submission #298319

---

Source Code Expand

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

string mp[12];

typedef pair<int,int> P;

const int di[4] = {-1,1,0,0};
const int dj[4] = {0,0,-1,1};

bool visited[12][12];
bool is_connected(int si, int sj) {
  memset(visited, 0, sizeof visited);
  queue<P> Q;
  Q.push(P(si, sj));

  while (!Q.empty()) {

    P p = Q.front(); Q.pop();
    int ci = p.first, cj = p.second;

    if (visited[ci][cj]) continue;

    //printf("%d,%d pop!\n", ci, cj);

    visited[ci][cj] = true;

    for(int i = 0; i < 4;i++) {
      int ni = ci + di[i], nj = cj + dj[i];
      if (ni < 0 || nj < 0 || 10 <= ni || 10 <= nj || mp[ni][nj] == 'x') continue;
      if (visited[ni][nj]) continue;
      Q.push(P(ni, nj));
    }
  }

  // chck

  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
      if (mp[i][j] == 'o' && !visited[i][j]) {
        //printf("%d-%d : false by %d,%d\n", si, sj, i, j);
        return false;
      }
    }
  }

  return true;
}

int solve() {

  int si = -1, sj = -1;
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
      if (mp[i][j] == 'o') {
        si = i, sj = j;
        break;
      }
    }
    if (si != -1) break;
  }

  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
      if (mp[i][j] == 'x') {
        mp[i][j] = 'o';
        //printf("call by %d,%d\n", i, j);

        //for (int k = 0; k < 10; k++) cout << mp[k] << endl;

        if (is_connected(si, sj)) return 1;
        mp[i][j] = 'x';
      }
    }
  }

  return 0;
}

int main() {
  while (cin >> mp[0]) {
    for (int i = 1; i < 10; i++) {
      cin >> mp[i];
    }
    printf("%s\n", solve() ? "YES" : "NO");
  }
  return 0;
}

Submission Info

Judge Result