Submission #309290

---

Source Code Expand

// #define _CRT_SECURE_NO_WARNINGS
// #define _USE_MATH_DEFINES
#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 multimap<int, char, greater<int> > MuMAPIC;
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++)
#define foreach_it(type,it,c) for(type::iterator it=c.begin(),c_end=c.end();it!=c_end;++it)
#define DUMP_VVI(b) FOR(i,0,b.size()){FOR(j,0,b[i].size())printf("%d ",b[i][j]);puts("");}
// 入力をpush_back(d)やarray[d]に使う時に1行で書ける
// int INPUT_INT() {int d;cin>>d;return d;}
template<class T>T IN(){T d;cin>>d;return d;}

// -------------------- include, typedef, define, template 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] = {};	// reverse hash.

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

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

int solve(int R, int C){
	int ans=0;
	// HU : 左上, MS : 右下, dis : distance from the center line.
	FOR(HU_c,0,C-1){
		FOR(MS_c,HU_c+1,C){
			// 高さが奇数(1,3,5,...)の四角形
			FOR(i,0,R){
				// 中央1行チェック
				if(Get_hash1(i,HU_c,MS_c) != Get_hash2(i,HU_c,MS_c))
					continue;	// 次のiへ.
				for(int dis=1; i-dis>=0, i+dis<R; dis++){
					// 今見る四角形(最上行i-dis, 最下行i+dis)が、fieldに収まっているなら実行.
					if(Get_hash1(i-dis,HU_c,MS_c) == Get_hash2(i+dis,HU_c,MS_c))
						ans++;
					else
						break;
				}
			}
			// 高さが偶数(2,4,6,...)の四角形
			FOR(i,0,R){
				for(int dis=1; i-dis +1 >=0, i+dis<R; dis++){
					// 今見る四角形(最上行i-dis+1, 最下行i+dis)が、fieldに収まっているか.
					if(Get_hash1(i-dis +1 ,HU_c,MS_c) == Get_hash2(i+dis,HU_c,MS_c))
						ans++;
					else
						break;
				}
			}
		}
	}
	return ans;
}

// 以下のURL先のコードに大変お世話になりました.
// http://code-thanks-festival-2014-a-open.contest.atcoder.jp/submissions/294369
// 解法：4重ループにする,ローリングハッシュを書く.

int main(){
	fastIO;
	int R = 0, C = 0;

	cin >> R >> C;
	vector<string> field;
	field.reserve(R);
	FOR(i,0,R)
		field.push_back(IN<string>());

	base_pow[0]=1;
	FOR(i,0,C)
		base_pow[i+1] = base_pow[i] * base;

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

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

Submission Info

Judge Result