0116:Rectangular Searching

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0116

典型問題。↓を参考にした。
http://algorithms.blog55.fc2.com/blog-entry-133.html

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>

using namespace std;

typedef pair<int,int> pii;

char G[501][501];
int g[501][501];

int main(void){

	int h,w;
	while(cin >> h >> w,h|w){
		fill(g[0],g[501],0);
		for(int i=0;i<h;i++)cin >> G[i];

		for(int i=0;i<w;i++)g[0][i]=(G[0][i]=='.');
		for(int i=1;i<h;i++){
			for(int j=0;j<w;j++){
				if(G[i][j]=='.')g[i][j]=g[i-1][j]+1;
			}
		}

		int ans=0;
		for(int i=0;i<h;i++){
			stack<pii> st;
			for(int j=0;j<w;j++){
				if(st.empty() || st.top().first<g[i][j])st.push(pii(g[i][j],j));
				else if(st.top().first>g[i][j]){
					int pos;
					while(!st.empty() && st.top().first>=g[i][j]){
						pos=st.top().second;
						ans=max(ans,(j-st.top().second)*st.top().first);
						st.pop();
					}
					st.push(pii(g[i][j],pos));
				}
			}
			
			while(!st.empty()){
				ans=max(ans,(w-st.top().second)*st.top().first);
				st.pop();
			}
			
		}
		cout << ans << endl;
	}

	return 0;
}