AcWing 152. Java 悬线法 城市游戏
原题链接
中等
作者:
henhen敲
,
2020-06-19 00:35:00
,
所有人可见
,
阅读 922
悬线法 通俗的讲 就是从矩阵中每一点发出一条射线 要么撞到障碍点 要么撞到矩阵边界 然后求出以该射线的长度
为长 从左右选出适合的点连成宽 所围成的最大矩形面积
import java.io.*;
import java.util.*;
class Main{
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int nextInt() throws Exception{
in.nextToken();
return (int)in.nval;
}
static String next()throws Exception{
in.nextToken();
return in.sval;
}
public static void main(String[] args) throws Exception{
int n, m;
n = nextInt(); m = nextInt();
int[][] g =new int[n][m];
int max = 0;
int[][] left, right, up;
left = new int[n][m];
right = new int[n][m];
up = new int[n][m];
for(int i=0; i<n; i++)
for(int j=0; j<m; j++){
String t = next();
g[i][j] = t.equals("F")?1:0;
left[i][j] = j; right[i][j] = j;
up[i][j] = 1;
}
for(int i=0; i<n; i++)
for(int j=1; j<m; j++)
if(g[i][j]!=0&&g[i][j-1]!=0) left[i][j] = left[i][j-1];
for(int i=0; i<n; i++)
for(int j=m-2; j>=0; j--)
if(g[i][j]!=0&&g[i][j+1]!=0) right[i][j] = right[i][j+1];
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
if(g[i][j]!=0){
int l, r;
l = left[i][j]; r = right[i][j];
if(i>0&&g[i-1][j]!=0){
up[i][j] = up[i-1][j] + 1;
l = Math.max(l, left[i-1][j]);
r = Math.min(r, right[i-1][j]);
}
left[i][j] = l;
right[i][j] = r;
max = Math.max((r-l+1)*up[i][j], max);
}
out.println(max*3);
out.close();
}
}