Advertisement
Vince14

Untitled

Mar 19th, 2023
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.24 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <stack>
  10. #include <queue>
  11. #include <deque>
  12. #include <unordered_map>
  13. #include <iomanip>
  14. #include <regex>
  15. #include <numeric>
  16. using namespace std;
  17. #define pii pair<long long , long long>
  18. #define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
  19. const long long dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
  20. const long long MAX = 305;
  21. const long long MOD = 1000000009;
  22.  
  23. int n, m, l;
  24. string s;
  25. int arr[MAX][MAX];
  26. int hsum[MAX][MAX][26], vsum[MAX][MAX][26];
  27. int nxt[MAX][MAX][26];
  28.  
  29. void init_hsum(){
  30. for(int i = 0; i < n; i++){
  31. for(int j = 0; j < m; j++){
  32. if(j == 0){
  33. int cur = arr[i][j];
  34. hsum[i][j][cur] = 1;
  35. }
  36. else {
  37. int cur = arr[i][j];
  38. for(int k = 0; k < 26; k++){
  39. if(k == cur){
  40. hsum[i][j][k] = hsum[i][j - 1][k] + 1;
  41. }
  42. else{
  43. hsum[i][j][k] = hsum[i][j - 1][k];
  44. }
  45. }
  46. }
  47. }
  48. }
  49. }
  50.  
  51. void init_vsum(){
  52. for(int j = 0; j < m; j++){
  53. for(int i = 0; i < n; i++){
  54. if(i == 0){
  55. int cur = arr[i][j];
  56. for(int k = 0; k < 26; k++){
  57. if(k == cur){
  58. vsum[i][j][k] = 1;
  59. }
  60. else{
  61. vsum[i][j][k] = 0;
  62. }
  63. }
  64. }
  65. else {
  66. int cur = arr[i][j];
  67. for(int k = 0; k < 26; k++){
  68. if(k == cur){
  69. vsum[i][j][k] = vsum[i - 1][j][k] + 1;
  70. }
  71. else{
  72. vsum[i][j][k] = vsum[i - 1][j][k];
  73. }
  74. }
  75. }
  76. }
  77. }
  78. }
  79.  
  80. int main() {
  81. //freopen("hayfeast.in", "r", stdin);
  82. //freopen("hayfeast.out", "w", stdout);
  83. FAST;
  84. cin >> n >> m >> l;
  85. cin >> s;
  86. for(int i = 0; i < n; i++){
  87. string tmp;
  88. cin >> tmp;
  89. for(int j = 0; j < tmp.size(); j++){
  90. arr[i][j] = tmp[j] - 'A';
  91. }
  92. }
  93. init_hsum();
  94. init_vsum();
  95. for(int i = 2; i < n; i++){
  96. if(2 >= n){
  97. break;
  98. }
  99. for(int k = 0; k < 26; k++){
  100. if(i == 2){
  101. nxt[0][0][k] += hsum[i][m - 1][k] - hsum[i][2][k];
  102. }
  103. else{
  104. nxt[0][0][k] += hsum[i][m - 1][k] - hsum[i][1][k];
  105. }
  106. }
  107. }
  108. // Add 1st line horizontal movement
  109.  
  110.  
  111. // vertical movement (going down array)
  112. for(int i = 1; i < n; i++){
  113. int j = 0;
  114. for(int k = 0; k < 26; k++){
  115. nxt[i][j][k] = nxt[i - 1][j][k];
  116. if(i - 3 >= 0){
  117. if(j - 2 >= 0){
  118. nxt[i][j][k] += (arr[i - 3][j - 2] == k) ? 1 : 0;
  119. }
  120. if(j + 2 < m){
  121. nxt[i][j][k] += (arr[i - 3][j + 2] == k) ? 1 : 0;
  122. }
  123. }
  124. if(i - 2 >= 0){
  125. if(j - 3 >= 0){
  126. nxt[i][j][k] += hsum[i - 2][j - 3][k];
  127. }
  128. if(j + 3 < m){
  129. nxt[i][j][k] += hsum[i - 2][m - 1][k] - hsum[i - 2][j + 2][k];
  130. }
  131. }
  132. if(i + 1 < n){
  133. if(j - 3 >= 0){
  134. nxt[i][j][k] -= hsum[i + 1][j - 3][k];
  135. }
  136. if(j + 3 < m){
  137. nxt[i][j][k] -= hsum[i + 1][m - 1][k] - hsum[i + 1][j + 2][k];
  138. }
  139. }
  140. if(i + 2 < n){
  141. if(j - 2 >= 0){
  142. nxt[i][j][k] -= (arr[i + 2][j - 2] == k) ? 1 : 0;
  143. }
  144. if(j + 2 < m){
  145. nxt[i][j][k] -= (arr[i + 2][j + 2] == k) ? 1 : 0;
  146. }
  147. }
  148. }
  149. }
  150. for(int i = 0; i < n; i++){
  151. cout << nxt[i][0][0] << "\n";
  152. }
  153.  
  154. }
  155. // 5 10
  156. //4 10
  157. //6 15
  158. //3 5
  159. //4 9
  160. //3 6
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement