Submission #308803

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// #define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <locale>
#include <cctype>
#include <sstream>
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef map<int, int> MAPII;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

// #define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <locale>
#include <cctype>
#include <sstream>
using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef map<int, int> MAPII;
typedef vector<pair<int, int> > VPII;
typedef multimap<int, string, greater<int> > MuMIS;

#define MP make_pair
#define fastIO  cin.tie(0); ios::sync_with_stdio(false);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
//for gcc (未test)
// #define FOREACH_IT(it,c) for(typeof(c)::iterator it=(c).begin(); it!=(c).end(); ++it)
//for Visual Studio
#define foreach_it(type,it,c) for(type::iterator it=c.begin(),c_end=c.end();it!=c_end;++it)
// 未test
#define DUMP_VVI(b) FOR(i,0,b.size()){FOR(j,0,b[i].size())printf("%d ",b[i][j]);puts("");}

// ------------------- include, typedef, define END. -------------------

LL base = 1000000009;
LL base_pow[255];	// C<=250なので余裕持って255. base_pow[i] = base^i.
LL hash1[255][255] = {};
LL hash2_rev[255][255] = {};

LL Get_hash1(int HU_r, int HU_c, int MS_r, int MS_c){
	// MS_rは使い道ない
	// cout <<"HU_c-1 = " << HU_c-1<<endl;
	return hash1[HU_r][MS_c] - hash1[HU_r][HU_c-1] * base_pow[MS_c-HU_c+1];
}

LL Get_hash2(int HU_r, int HU_c, int MS_r, int MS_c){
	// HU_rは使い道ない
	return hash2_rev[MS_r][HU_c] - hash2_rev[MS_r][MS_c+1] * base_pow[MS_c-HU_c+1];
}

bool Check2(int HU_r, int HU_c, int MS_r, int MS_c){
	bool ret = true;
	int i=0;
	while(HU_r+i <= MS_r-i){
//		cout<<endl;
//		cout << "	now ("<< HU_r+i<<", "<<HU_c<<") ～ ("<<MS_r-i<<", "<<MS_c<<")";
		LL nowHash1 = Get_hash1(HU_r+i,HU_c,MS_r-i,MS_c);
		LL nowHash2 = Get_hash2(HU_r+i,HU_c,MS_r-i,MS_c);
//		cout << "	now hash1 = "<<nowHash1 <<endl<<
//			"				now hash2 = "<< nowHash2;
		if(nowHash1 != nowHash2){
//			cout<<" ← false"<<endl;
			return false;
		}
		i++;
	}
//	cout<<" ← true HITS!!" << endl;
//	cout << "hash1 = "<<Get_hash1(HU_r+i,HU_c,MS_r-i,MS_c)<<endl<<
//		"hash2 = "<<Get_hash2(HU_r+i,HU_c,MS_r-i,MS_c)<<endl;
	return ret;
}

int solve(int R, int C, vector<string> &field){
	int ans = 0;
	// HU : 左上  MS : 右下
	FOR(HU_r, 0, field.size()){
		FOR(HU_c, 0, C - 1){
			FOR(MS_r, HU_r + 1, field.size()){
				FOR(MS_c, HU_c + 1, field[HU_r].size()){
//					cout << "check (" << HU_r << ", " << HU_c << ") ～ (" << MS_r << ", " << MS_c << ")";
//					cout << endl;
					if (Check2(HU_r, HU_c, MS_r, MS_c))
						ans++;

				}
			}
		}
	}
	return ans;
}

// http://code-thanks-festival-2014-a-open.contest.atcoder.jp/submissions/294369

int main(){
	fastIO;
	int R = 0, C = 0;
	string temp;
	// 入力
	cin >> R >> C;
	vector<string> field;
	field.reserve(R);
	FOR(i, 0, R){
		cin >> temp;
		field.push_back(temp);
	}
	// 入力おわり
	// ハッシュ計算用
	base_pow[0]=1;
	FOR(i,0,C){
		base_pow[i+1] = base_pow[i] * base;
		// cout<<"base_pow["<<i+1<<"] = "<<base_pow[i+1]<<endl;
	}

	FOR(i,0,R){
		FOR(j,0,C){
			if(j==0)	hash1[i][j] = 0 + field[i][j];
			else		hash1[i][j] = hash1[i][j-1] * base + field[i][j];
			// hash1[i][j+1] = hash1[i][j] * base + field[i][j];
			// cout<<"hash1["<<i<<"]["<<j+1<<"] = "<<hash1[i][j+1]<<endl;
		}
		for(int j=C-1; j>=0; j--){
			hash2_rev[i][j] = hash2_rev[i][j+1] * base + field[i][j];
			// cout<<"hash2_rev["<<i<<"]["<<j-1<<"] = "<<hash2_rev[i][j-1]<<endl;
		}
	}

	cout << solve(R, C, field) << endl;
	return 0;
}

Submission Info

Judge Result