fork download
copy 
  1. /*
  2.         check korbo je amader oi grid e 1 er beshi black cell ase kina
  3.                 if no: Yes
  4.                 if yes:
  5.                 1) amader oi grid e por por 3ta consecutive
  6.    cell ase kina jegula black
  7.                 if yes: no
  8.                                 if no:
  9.  
  10.   0 1 2
  11. 0 . # .
  12. 1 . # #
  13. 2 . . .
  14.  
  15.  
  16.  
  17. */
  18.  
  19. #include <bits/stdc++.h>
  20. using namespace std;
  21.  
  22. bool up_right_and_left_bottom(vector<vector<char>>& grid, int black_cell_cnt,
  23.                               int first_black_cell_row,
  24.                               int first_black_cell_col) {
  25.   int count = 1;
  26.   int n = grid.size();
  27.  
  28.   int i = first_black_cell_row;
  29.   int j = first_black_cell_col;
  30.  
  31.   bool now_at_up = true;
  32.   bool now_at_right = false;
  33.  
  34.   while (true) {
  35.     if (now_at_up == true) {
  36.       i--;
  37.       if (i >= 0 && i < n && j >= 0 && j < n) {
  38.         now_at_up = false;
  39.         now_at_right = true;
  40.         if (grid[i][j] == '#') {
  41.           count++;
  42.         }
  43.       } else {
  44.         break;
  45.       }
  46.     } else if (now_at_right == true) {
  47.       j++;
  48.       if (i >= 0 && i < n && j >= 0 && j < n) {
  49.         now_at_up = true;
  50.         now_at_right = false;
  51.         if (grid[i][j] == '#') {
  52.           count++;
  53.         }
  54.       } else {
  55.         break;
  56.       }
  57.     }
  58.   }
  59.  
  60.   i = first_black_cell_row;
  61.   j = first_black_cell_col;
  62.  
  63.   bool now_at_left = true;
  64.   bool now_at_bottom = false;
  65.  
  66.   while (true) {
  67.     if (now_at_left == true) {
  68.       j--;
  69.       if (i >= 0 && i < n && j >= 0 && j < n) {
  70.         now_at_left = false;
  71.         now_at_bottom = true;
  72.         if (grid[i][j] == '#') {
  73.           count++;
  74.         }
  75.       } else {
  76.         break;
  77.       }
  78.     } else if (now_at_bottom == true) {
  79.       i++;
  80.       if (i >= 0 && i < n && j >= 0 && j < n) {
  81.         now_at_left = true;
  82.         now_at_bottom = false;
  83.         if (grid[i][j] == '#') {
  84.           count++;
  85.         }
  86.       } else {
  87.         break;
  88.       }
  89.     }
  90.   }
  91.  
  92.   if (count == black_cell_cnt) {
  93.     return true;
  94.   } else {
  95.     return false;
  96.   }
  97. }
  98.  
  99. bool right_top_and_bottom_left(vector<vector<char>>& grid, int black_cell_cnt,
  100.                                int first_black_cell_row,
  101.                                int first_black_cell_col) {
  102.   int count = 1;
  103.   int n = grid.size();
  104.  
  105.   int i = first_black_cell_row;
  106.   int j = first_black_cell_col;
  107.  
  108.   bool now_at_right = true;
  109.   bool now_at_top = false;
  110.  
  111.   while (true) {
  112.     if (now_at_right == true) {
  113.       j++;
  114.       if (i >= 0 && i < n && j >= 0 && j < n) {
  115.         now_at_right = false;
  116.         now_at_top = true;
  117.         if (grid[i][j] == '#') {
  118.           count++;
  119.         }
  120.       } else {
  121.         break;
  122.       }
  123.     } else if (now_at_top == true) {
  124.       i--;
  125.       if (i >= 0 && i < n && j >= 0 && j < n) {
  126.         now_at_right = true;
  127.         now_at_top = false;
  128.         if (grid[i][j] == '#') {
  129.           count++;
  130.         }
  131.       } else {
  132.         break;
  133.       }
  134.     }
  135.   }
  136.  
  137.   i = first_black_cell_row;
  138.   j = first_black_cell_col;
  139.  
  140.   bool now_at_bottom = true;
  141.   bool now_at_left = false;
  142.  
  143.   while (true) {
  144.     if (now_at_bottom == true) {
  145.       i++;
  146.       if (i >= 0 && i < n && j >= 0 && j < n) {
  147.         now_at_bottom = false;
  148.         now_at_left = true;
  149.         if (grid[i][j] == '#') {
  150.           count++;
  151.         }
  152.       } else {
  153.         break;
  154.       }
  155.     } else if (now_at_left == true) {
  156.       j--;
  157.       if (i >= 0 && i < n && j >= 0 && j < n) {
  158.         now_at_bottom = true;
  159.         now_at_left = false;
  160.         if (grid[i][j] == '#') {
  161.           count++;
  162.         }
  163.       } else {
  164.         break;
  165.       }
  166.     }
  167.   }
  168.  
  169.   if (count == black_cell_cnt) {
  170.     return true;
  171.   } else {
  172.     return false;
  173.   }
  174. }
  175.  
  176. bool left_top_and_bottom_right(vector<vector<char>>& grid, int black_cell_cnt,
  177.                                int first_black_cell_row,
  178.                                int first_black_cell_col) {
  179.   int count = 1;
  180.   int n = grid.size();
  181.  
  182.   int i = first_black_cell_row;
  183.   int j = first_black_cell_col;
  184.  
  185.   bool now_at_left = true;
  186.   bool now_at_top = false;
  187.  
  188.   while (true) {
  189.     if (now_at_left == true) {
  190.       j--;
  191.       if (i >= 0 && i < n && j >= 0 && j < n) {
  192.         now_at_left = false;
  193.         now_at_top = true;
  194.         if (grid[i][j] == '#') {
  195.           count++;
  196.         }
  197.       } else {
  198.         break;
  199.       }
  200.     } else if (now_at_top == true) {
  201.       i--;
  202.       if (i >= 0 && i < n && j >= 0 && j < n) {
  203.         now_at_left = true;
  204.         now_at_top = false;
  205.         if (grid[i][j] == '#') {
  206.           count++;
  207.         }
  208.       } else {
  209.         break;
  210.       }
  211.     }
  212.   }
  213.  
  214.   i = first_black_cell_row;
  215.   j = first_black_cell_col;
  216.  
  217.   bool now_at_bottom = true;
  218.   bool now_at_right = false;
  219.  
  220.   while (true) {
  221.     if (now_at_bottom == true) {
  222.       i++;
  223.       if (i >= 0 && i < n && j >= 0 && j < n) {
  224.         now_at_bottom = false;
  225.         now_at_right = true;
  226.         if (grid[i][j] == '#') {
  227.           count++;
  228.         }
  229.       } else {
  230.         break;
  231.       }
  232.     } else if (now_at_right == true) {
  233.       j++;
  234.       if (i >= 0 && i < n && j >= 0 && j < n) {
  235.         now_at_bottom = true;
  236.         now_at_right = false;
  237.         if (grid[i][j] == '#') {
  238.           count++;
  239.         }
  240.       } else {
  241.         break;
  242.       }
  243.     }
  244.   }
  245.  
  246.   if (count == black_cell_cnt) {
  247.     return true;
  248.   } else {
  249.     return false;
  250.   }
  251. }
  252.  
  253. bool up_left_and_right_bottom(vector<vector<char>>& grid, int black_cell_cnt,
  254.                               int first_black_cell_row,
  255.                               int first_black_cell_col) {
  256.   int count = 1;
  257.   int n = grid.size();
  258.  
  259.   int i = first_black_cell_row;
  260.   int j = first_black_cell_col;
  261.  
  262.   bool now_at_up = true;
  263.   bool now_at_left = false;
  264.  
  265.   while (true) {
  266.     if (now_at_up == true) {
  267.       i--;
  268.       if (i >= 0 && i < n && j >= 0 && j < n) {
  269.         now_at_up = false;
  270.         now_at_left = true;
  271.         if (grid[i][j] == '#') {
  272.           count++;
  273.         }
  274.       } else {
  275.         break;
  276.       }
  277.     } else if (now_at_left == true) {
  278.       j--;
  279.       if (i >= 0 && i < n && j >= 0 && j < n) {
  280.         now_at_up = true;
  281.         now_at_left = false;
  282.         if (grid[i][j] == '#') {
  283.           count++;
  284.         }
  285.       } else {
  286.         break;
  287.       }
  288.     }
  289.   }
  290.  
  291.   i = first_black_cell_row;
  292.   j = first_black_cell_col;
  293.  
  294.   bool now_at_right = true;
  295.   bool now_at_bottom = false;
  296.  
  297.   while (true) {
  298.     if (now_at_right == true) {
  299.       j++;
  300.       if (i >= 0 && i < n && j >= 0 && j < n) {
  301.         now_at_right = false;
  302.         now_at_bottom = true;
  303.         if (grid[i][j] == '#') {
  304.           count++;
  305.         }
  306.       } else {
  307.         break;
  308.       }
  309.     } else if (now_at_bottom == true) {
  310.       i++;
  311.       if (i >= 0 && i < n && j >= 0 && j < n) {
  312.         now_at_right = true;
  313.         now_at_bottom = false;
  314.         if (grid[i][j] == '#') {
  315.           count++;
  316.         }
  317.       } else {
  318.         break;
  319.       }
  320.     }
  321.   }
  322.  
  323.   if (count == black_cell_cnt) {
  324.     return true;
  325.   } else {
  326.     return false;
  327.   }
  328. }
  329.  
  330. void solve() {
  331.   int n;
  332.   cin >> n;
  333.   vector<vector<char>> grid(n);
  334.  
  335.   int first_black_cell_row = -1;
  336.   int first_black_cell_col = -1;
  337.  
  338.   int black_cell_cnt = 0;
  339.  
  340.   for (int i = 0; i < n; ++i) {
  341.     for (int j = 0; j < n; ++j) {
  342.       char x;
  343.       cin >> x;
  344.       grid[i].push_back(x);
  345.  
  346.       if (grid[i][j] == '#') {
  347.         black_cell_cnt++;
  348.       }
  349.       if (grid[i][j] == '#' && first_black_cell_row == -1 &&
  350.           first_black_cell_col == -1) {
  351.         first_black_cell_row = i;
  352.         first_black_cell_col = j;
  353.       }
  354.     }
  355.   }
  356.  
  357.   if (black_cell_cnt < 2 || n <= 2) {
  358.     cout << "YES" << endl;
  359.   } else {
  360.     // check three consecutive cell black or not;
  361.     bool is_there_consecutive_cell_black = false;
  362.     for (int i = 0; i < n; ++i) {
  363.       for (int j = 0; j < n - 2; ++j) {
  364.         if (grid[i][j] == '#' && grid[i][j + 1] == '#' &&
  365.             grid[i][j + 2] == '#') {
  366.           is_there_consecutive_cell_black = true;
  367.           break;
  368.         }
  369.       }
  370.     }
  371.     if (is_there_consecutive_cell_black != true) {
  372.       for (int i = 0; i < n; ++i) {
  373.         for (int j = 0; j < n - 2; ++j) {
  374.           if (grid[j][i] == '#' && grid[j + 1][i] == '#' &&
  375.               grid[j + 2][i] == '#') {
  376.             is_there_consecutive_cell_black = true;
  377.             break;
  378.           }
  379.         }
  380.         if (is_there_consecutive_cell_black) break;
  381.       }
  382.     }
  383.  
  384.     if (is_there_consecutive_cell_black) {
  385.       cout << "NO" << endl;
  386.     } else {
  387.       if (up_right_and_left_bottom(grid, black_cell_cnt, first_black_cell_row,
  388.                                    first_black_cell_col) == true ||
  389.           right_top_and_bottom_left(grid, black_cell_cnt, first_black_cell_row,
  390.                                     first_black_cell_col) == true ||
  391.           up_left_and_right_bottom(grid, black_cell_cnt, first_black_cell_row,
  392.                                    first_black_cell_col) == true ||
  393.           left_top_and_bottom_right(grid, black_cell_cnt, first_black_cell_row,
  394.                                     first_black_cell_col) == true) {
  395.         cout << "YES" << endl;
  396.       } else {
  397.         cout << "NO" << endl;
  398.       }
  399.     }
  400.   }
  401. }
  402.  
  403. int main() {
  404.   int t;
  405.   cin >> t;
  406.   while (t--) {
  407.     solve();
  408.   }
  409. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
11
1
.
1
#
3
.##
.##
...
3
#..
.#.
..#
3
###
...
...
3
#.#
...
.#.
4
####
#..#
#..#
####
3
..#
...
.#.
3
..#
#..
...
5
#.#.#
.#.#.
#.#.#
.#.#.
#.#.#
5
...#.
...#.
.....
##...
.....
stdout
copy 
YES
YES
NO
YES
NO
NO
NO
YES
YES
NO
YES
https://ideone.com/Fr08ra
language:
C++14 (gcc 8.3)
created:
1 day 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!