Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <cstring>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <set>
- #include <map>
- #include <stack>
- #include <queue>
- #include <deque>
- #include <unordered_map>
- #include <iomanip>
- #include <regex>
- #include <numeric>
- using namespace std;
- #define pii pair<long long , long long>
- #define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
- const long long dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
- const long long MAX = 305;
- const long long MOD = 1000000009;
- int n, m, l;
- string s;
- int arr[MAX][MAX];
- int hsum[MAX][MAX][26], vsum[MAX][MAX][26];
- int nxt[MAX][MAX][26];
- void init_hsum(){
- for(int i = 0; i < n; i++){
- for(int j = 0; j < m; j++){
- if(j == 0){
- int cur = arr[i][j];
- hsum[i][j][cur] = 1;
- }
- else {
- int cur = arr[i][j];
- for(int k = 0; k < 26; k++){
- if(k == cur){
- hsum[i][j][k] = hsum[i][j - 1][k] + 1;
- }
- else{
- hsum[i][j][k] = hsum[i][j - 1][k];
- }
- }
- }
- }
- }
- }
- void init_vsum(){
- for(int j = 0; j < m; j++){
- for(int i = 0; i < n; i++){
- if(i == 0){
- int cur = arr[i][j];
- for(int k = 0; k < 26; k++){
- if(k == cur){
- vsum[i][j][k] = 1;
- }
- else{
- vsum[i][j][k] = 0;
- }
- }
- }
- else {
- int cur = arr[i][j];
- for(int k = 0; k < 26; k++){
- if(k == cur){
- vsum[i][j][k] = vsum[i - 1][j][k] + 1;
- }
- else{
- vsum[i][j][k] = vsum[i - 1][j][k];
- }
- }
- }
- }
- }
- }
- int main() {
- //freopen("hayfeast.in", "r", stdin);
- //freopen("hayfeast.out", "w", stdout);
- FAST;
- cin >> n >> m >> l;
- cin >> s;
- for(int i = 0; i < n; i++){
- string tmp;
- cin >> tmp;
- for(int j = 0; j < tmp.size(); j++){
- arr[i][j] = tmp[j] - 'A';
- }
- }
- init_hsum();
- init_vsum();
- for(int i = 2; i < n; i++){
- if(2 >= n){
- break;
- }
- for(int k = 0; k < 26; k++){
- if(i == 2){
- nxt[0][0][k] += hsum[i][m - 1][k] - hsum[i][2][k];
- }
- else{
- nxt[0][0][k] += hsum[i][m - 1][k] - hsum[i][1][k];
- }
- }
- }
- // Add 1st line horizontal movement
- // vertical movement (going down array)
- for(int i = 1; i < n; i++){
- int j = 0;
- for(int k = 0; k < 26; k++){
- nxt[i][j][k] = nxt[i - 1][j][k];
- if(i - 3 >= 0){
- if(j - 2 >= 0){
- nxt[i][j][k] += (arr[i - 3][j - 2] == k) ? 1 : 0;
- }
- if(j + 2 < m){
- nxt[i][j][k] += (arr[i - 3][j + 2] == k) ? 1 : 0;
- }
- }
- if(i - 2 >= 0){
- if(j - 3 >= 0){
- nxt[i][j][k] += hsum[i - 2][j - 3][k];
- }
- if(j + 3 < m){
- nxt[i][j][k] += hsum[i - 2][m - 1][k] - hsum[i - 2][j + 2][k];
- }
- }
- if(i + 1 < n){
- if(j - 3 >= 0){
- nxt[i][j][k] -= hsum[i + 1][j - 3][k];
- }
- if(j + 3 < m){
- nxt[i][j][k] -= hsum[i + 1][m - 1][k] - hsum[i + 1][j + 2][k];
- }
- }
- if(i + 2 < n){
- if(j - 2 >= 0){
- nxt[i][j][k] -= (arr[i + 2][j - 2] == k) ? 1 : 0;
- }
- if(j + 2 < m){
- nxt[i][j][k] -= (arr[i + 2][j + 2] == k) ? 1 : 0;
- }
- }
- }
- }
- for(int i = 0; i < n; i++){
- cout << nxt[i][0][0] << "\n";
- }
- }
- // 5 10
- //4 10
- //6 15
- //3 5
- //4 9
- //3 6
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement