fork download
copy 
  1. #define CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <bits/stdc++.h>
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6.  
  7. using namespace __gnu_pbds;
  8. using namespace std;
  9. typedef long long ll;
  10. typedef long double ld;
  11. typedef unsigned long long ull;
  12. #define ordered_set tree<pair<ll,ll>, null_type, less <pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update>
  13. #define ll long long
  14. #define all(name)  name.begin(),name.end()
  15. #define rall(name)  name.rbegin(),name.rend()
  16. #define sz(s) (int)s.size()
  17. const int N = 2e6 + 10, mod = 1e9 + 7;
  18. const double PI = asin(1.0) * 2;
  19. const int OO = 0x3f3f3f3f;
  20. int dx[]{1, -1, 0, 0, 1, 1, -1, -1};
  21. int dy[]{0, 0, 1, -1, 1, -1, 1, -1};
  22.  
  23. void fast() {
  24.     std::ios_base::sync_with_stdio(0);
  25.     cin.tie(0);
  26.     cout.tie(0);
  27. }
  28.  
  29. map<string, bool> mp;
  30.  
  31. bool isWin(string s) {
  32.     return (
  33.             // row
  34.             (s[0] != '.' && s[0] == s[1] && s[0] == s[2]) ||
  35.             (s[3] != '.' && s[3] == s[4] && s[3] == s[5]) ||
  36.             (s[6] != '.' && s[6] == s[7] && s[6] == s[8]) ||
  37.             // col
  38.             (s[0] != '.' && s[0] == s[3] && s[0] == s[6]) ||
  39.             (s[1] != '.' && s[1] == s[4] && s[1] == s[7]) ||
  40.             (s[2] != '.' && s[2] == s[5] && s[2] == s[8]) ||
  41.             // diag
  42.             (s[0] != '.' && s[0] == s[4] && s[0] == s[8]) ||
  43.             (s[0] != '.' && s[2] == s[4] && s[2] == s[6])
  44.     );
  45. }
  46.  
  47. string ans;
  48. bool ck = 0;
  49.  
  50. void bfs(string s = ".........") {
  51.     ck = 0;
  52.     queue<pair<string, bool>> q; // grid, player( X --> 1, O --> 0)
  53.     q.push({s, 1});
  54.     while (!q.empty()) {
  55.         pair<string, bool> p = q.front();
  56.         q.pop();
  57.         string grid = p.first;
  58.         cout<<grid<<" "<<ans<<"\n";
  59.         if (grid == ans) {
  60.             ck = 1;
  61.             break;
  62.         }
  63.         if (!isWin(grid)) {
  64.             for (int i = 0; i < 9; i++) {
  65.                 if (grid[i] == '.') {
  66.                     if (p.second) grid[i] = 'X'; else grid[i] = 'O';
  67.                     if (grid[i] == ans[i])
  68.                         q.push({grid, p.second ^ 1});
  69.                     grid[i] = '.';
  70.                 }
  71.             }
  72.         }
  73.     }
  74. }
  75.  
  76. void solve() {
  77.     string s;
  78.     ans = "";
  79.     for (int i = 0; i < 3; i++) {
  80.         cin >> s;
  81.         ans += s;
  82.     }
  83.     bfs();
  84.     cout << (ck ? "yes" : "no") << "\n";
  85. }
  86.  
  87. int main() {
  88.     fast();
  89.     //freopen("abc.in", "r", stdin);
  90.     //freopen("output.txt", "w", stdout);
  91.     int T = 1;
  92.     cin >> T;
  93.     while (T--) {
  94.         solve();
  95.     }
  96.     return 0;
  97. }
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
1
O..
X..
...
stdout
copy 
......... O..X.....
...X..... O..X.....
O..X..... O..X.....
yes
https://ideone.com/iOWHH8
language:
C++ (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!