fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int countHorizontal(vector<string> &grid, int i, int j) {
  6. 	int cntHoriZontal = 0;
  7. 	for (int dx = 0; dx < grid.size(); dx++) {
  8. 		if (j + dx < grid.size()) {
  9. 			if (grid[i][j + dx] == 'X') {
  10. 				cntHoriZontal++;
  11. 			} else {
  12. 				break;
  13. 			}
  14. 		}
  15. 	}
  16. 	return cntHoriZontal;
  17. }
  18.  
  19. int countVertical(vector<string> &grid, int i, int j) {
  20. 	int cntVertical = 0;
  21. 	for (int dx = 0; dx < grid.size(); dx++) {
  22. 		if (i + dx < grid.size()) {
  23. 			if (grid[i + dx][j] == 'X') {
  24. 				cntVertical++;
  25. 			} else {
  26. 				break;
  27. 			}
  28. 		}
  29. 	}
  30. 	return cntVertical;
  31. }
  32.  
  33. int countOppositeDiagonal(vector<string> &grid, int i, int j) {
  34. 	int cnt = 0;
  35. 	for (int dx = 0; dx < grid.size(); dx++) {
  36. 		if (i + dx < grid.size() && j - dx >= 0) {
  37. 			if (grid[i + dx][j - dx] == 'X') {
  38. 				cnt++;
  39. 			} else {
  40. 				break;
  41. 			}
  42. 		}
  43. 	}
  44. 	return cnt;
  45. }
  46.  
  47. int countMainDiagonal(vector<string> &grid, int i, int j) {
  48. 	int cnt = 0;
  49. 	for (int dx = 0; dx < grid.size(); dx++) {
  50. 		if (i + dx < grid.size() && j + dx < grid.size()) {
  51. 			if (grid[i + dx][j + dx] == 'X') {
  52. 				cnt++;
  53. 			} else {
  54. 				break;
  55. 			}
  56. 		}
  57. 	}
  58. 	return cnt;
  59. }
  60.  
  61. int isWinning(vector<string> grid, int K) {
  62. 	for (int i = 0; i < grid.size(); i++) {
  63. 		for (int j = 0; j < grid[i].size(); j++) {
  64. 			// row
  65. 			if (countHorizontal(grid, i, j) >= K) {
  66. 				return true;
  67. 			}	
  68. 			// column
  69. 			if (countVertical(grid, i, j) >= K) {
  70. 				return true;
  71. 			}
  72. 			// main digoanal
  73. 			if (countMainDiagonal(grid, i, j) >= K) {
  74. 				return true;
  75. 			}
  76. 			// antigonal digoanal
  77. 			if (countOppositeDiagonal(grid, i, j) >= K) {
  78. 				return true;
  79. 			}
  80. 		}
  81. 	}
  82. 	return false;
  83. }
  84.  
  85. int canWin(vector<string> grid, int K) {
  86. 	for (int i = 0; i < grid.size(); i++) {
  87. 		for (int j = 0; j < grid[i].size(); j++) {
  88. 			if (grid[i][j] == '.') {
  89. 				vector<string> copyGrid = grid;
  90. 				copyGrid[i][j] = 'X';
  91. 				if (isWinning(copyGrid, K)) {
  92. 					return true;
  93. 				}
  94. 			}
  95. 		}
  96. 	}
  97. 	return false;
  98. }
  99.  
  100. int main() {
  101. 	int T;
  102. 	cin >> T;
  103. 	while (T--) {
  104. 		int N, K;
  105. 		cin >> N >> K;
  106. 		vector<string> grid;
  107. 		for (int i = 0; i < N; i++) {
  108. 			string s;
  109. 			cin >> s;
  110. 			grid.push_back(s);
  111. 		}
  112. 		puts(canWin(grid, K) ? "YES" : "NO");
  113. 	}
  114. 	return 0;
  115. }
Time limit exceeded #stdin #stdout 5s 790016KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IDZKLf
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

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!