记录编号	22045	评测结果	AAAAAAAAAA
题目名称	剪切矩形	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	0.399 s
提交时间	2010-11-16 19:24:33	内存使用	3.95 MiB

{纸 NOIP模拟2010-11-16
 数值递推 栈
 Author: yangbohua
 Time: 2010-11-16 19:26}

program rectangle;
var
  a:array[0..1001,0..1001] of longint;
  q,p:array[0..1001] of longint;
  n,m,i,j,h,t:longint;
  ans:int64;
  r:char;

function max(x,y:longint):longint;
begin
  if x>y
    then max:=x
    else max:=y;
end;

begin
  assign(input,'rectangle.in');
  reset(input);
  assign(output,'rectangle.out');
  rewrite(output);

  readln(n,m);
  for i:=1 to n do
  begin
    for j:=1 to m do
    begin
      read(r);
      if r='.'
        then a[i,j]:=a[i-1,j]+1
        else a[i,j]:=0;
    end;
    readln;
  end;

  ans:=0;
  for h:=1 to n do
  begin
    t:=0;
    q[0]:=0;
    p[0]:=0;
    for i:=1 to m+1 do
    begin
      if a[h,i]>q[t] then
      begin
        t:=t+1;
        q[t]:=a[h,i];
        p[t]:=i;
      end
      else
      begin
        if a[h,i]<q[t] then
        begin
          while a[h,i]<q[t] do
          begin
            ans:=ans+(((i-p[t])*(i-p[t]+1)) div 2)*(q[t]-max(a[h,i],q[t-1]));
            q[t]:=max(q[t-1],a[h,i]);
            if q[t]=q[t-1] then t:=t-1;
          end;
          if a[h,i]>q[t] then
          begin
            t:=t+1;
            q[t]:=a[h,i];
          end;
        end;
      end;
    end;
  end;

  writeln(ans);
  close(input);
  close(output);
end.