fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <bits/stdc++.h>
  3. #include <unordered_map>
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6. #define __ELWKEL__ ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr);
  7. #define testCase int t;cin>>t;while(t--)
  8. #define ll long long
  9. #define ull unsigned long long
  10. #define all(v) ((v).begin()), ((v).end())
  11. #define rall(v) ((v).rbegin()), ((v).rend())
  12. #define sz(v) ((int)((v).size()))
  13. #define INF 1000000000
  14. #define INFLL 1000000000000000000
  15. using namespace std;
  16. using namespace __gnu_pbds;
  17. template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  18. const int N = 5;
  19. char grid[N][N];
  20. int n ,cnt;
  21. //Bashof el constraints
  22. bool can(int i , int j){
  23.     if(grid[i][j] == 'X') return false;
  24.  
  25.     bool valid = 1;
  26.     for(int col = 0; col < j;col++){
  27.         if(grid[i][col]=='O') valid = 0;
  28.         else if(grid[i][col] == 'X') valid = 1;
  29.     }
  30.     if(!valid) return false;
  31.     for(int col = n-1; col > j;col--){
  32.         if(grid[i][col]=='O') valid = 0;
  33.         else if(grid[i][col] == 'X') valid = 1;
  34.     }
  35.     if(!valid) return false;
  36.     for(int row = 0 ;row < i;row++){
  37.         if(grid[row][j]=='O') valid = 0;
  38.         else if(grid[row][j]=='X') valid = 1;
  39.     }
  40.     if(!valid) return false;
  41.     for(int row = n-1 ;row > i;row--){
  42.         if(grid[row][j]=='O') valid = 0;
  43.         else if(grid[row][j]=='X') valid = 1;
  44.     }
  45.     if(!valid) return false;
  46.     return true;
  47. }
  48.  
  49.  
  50. void rec(int i , int j , int cur){
  51.     if(j == n) //last cell in row .... go to next row
  52.         return rec(i + 1 , 0 , cur) ,void();
  53.  
  54.     if(i == n) // end
  55.         return cnt = max(cnt , cur) , void();
  56.  
  57.     if(can(i , j)){
  58.         grid[i][j]='O';
  59.         rec(i , j + 1, cur + 1);
  60.         grid[i][j]='.';
  61.     }
  62.     rec(i , j + 1, cur);
  63. }
  64.  
  65. void solve(){
  66. string s ="";
  67.     while(true){
  68.         cin >> n;
  69.         if(!n) break;
  70.         cnt = 0;
  71.         for(int i = 0 ; i< n;i++){
  72.             for(int j = 0; j < n;j++)
  73.                 cin >> grid[i][j];
  74.         }
  75.         rec(0 , 0 , 0);
  76.         cout << s<< cnt ,s = "\n";
  77.     }
  78. }
  79.  
  80. int32_t main() {                /*____*/ __ELWKEL__ /*____*/
  81. //    testCase
  82.     solve();
  83. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
4
 .X..
 ....
 XX..
 ....
 2
 XX
 .X
 3
 .X.
 X.X
 .X.
 3
 ...
 .XX
 .XX
 4
 ....
 ....
 ....
 ....
 0
stdout
copy 
5
1
5
2
4
https://ideone.com/un9Xw0
language:
C++ (gcc 8.3)
created:
3 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!