# Topcoder SRM 616 Div2 T3 TwoLLogo 题解

/ 0评 / 0

Topcoder Single Round Match 616 Div 2 T3 题解

## 题目大意

• 必须是严格的 "L" 形状，不可以旋转；原图也不能旋转；
• 两条“线段”必须有正长度，并且长度要大于等于 2；
• 并且线段经过的所有点都必须是白色的。

• grid will contain between 2 and 30 elements, inclusive.
• All elements of grid will contain the same number of characters.
• Each element of grid will contain between 2 and 30 characters, inclusive.
• Each character of grid will be either '.' or '#'.
• Time limit (s): 3.000
• Memory limit (MB): 256

## 题目原文

Please note that this problem has a non-standard time limit: 3 seconds.

A yet unknown "LL Company" wants to design a logo. After a long discussion, company designers decided that the logo should consist of two letters L drawn in some way.

To start with something, designers drew N rows of M points each, one under another, so that these points form a rectangular grid. They also painted each point either white or black. Here is an example of what they could get for N = 4 and M = 5:

Designers agreed to draw each letter L as a union of a horizontal and a vertical line segment intersecting at their left and bottom ends, respectively. The segments must have positive lengths, and their endpoints must be white grid points. All grid points that lie on the segments must be white as well. For example, here are two valid placements of a letter:

233333

Note that neither the letters nor the grid can be rotated.

The final requirement is that the two letters should be disjoint. That is, no white point should lie on two segments belonging to different letters.

You are given the grid with N rows and M columns, encoded as a vector <string> grid with N elements, each containing M characters. Each character is either '.' or '#', meaning that the corresponding point is either white or black, respectively.

Return the number of different possible logos with two L's drawn on them according to the requirements. Two logos are considered different if there is a pair of points that is connected by a line segment in exactly one of the logos.

## 样例解释

{"....",
"...."}


Returns: 1

{".##..",
"...#.",
".#.#.",
"#...#"}


Returns: 3
This is the example from the problem statement. The three possible logos look as follows:

{"##############",
"##############",
"#.############",
"#.############",
"#.############",
"#.############",
"#.############",
"#.############",
"#.#####.######",
"#.#####.######",
"#.#####.######",
"#....##.######",
"#######.######",
"#######.######",
"#######.######",
"#######.######",
"#######.######",
"#######.######",
"#######......#",
"##############"}



Returns: 1350

9×3×10×5=1350

……

## 分析

• 第一种，坠简单的情况，直接累加（懒得画图，直接用公式了……）：
XOXOX \\
XOXOO \\
XOXXX \\
XOOOX \\
XXXXX
• 然后就是分类讨论几种特殊情况，也就是存在交集的，以以下这种为例：
XXXXXX \\
XOXXXX \\
XOXOXX \\
XOOOOX \\
XXXOXX \\
XXXOOO

## 代码

#include <bits/stdc++.h>
#define CLEAR(_) memset(_,0,sizeof(_))
#define CLEAR_MAX(_) memset(_,0x3f,sizeof(_))
#define CLEAR_MIN(_) memset(_,0x80,sizeof(_))
#define CLEAR_REG(_) memset(_,255,sizeof(_))

using namespace std;
const long long maxn=35;
long long n,m;
long long rght[maxn][maxn],up[maxn][maxn],ans;
vector <string> a;

template<class T> void checkmin(T &a,const T &b) { if (b<a) a=b; }
template<class T> void checkmax(T &a,const T &b) { if (b>a) a=b; }
class TwoLLogo {
public:
long long countWays( vector <string> grid ) ;
};

inline void init(){
ans=0;
CLEAR_REG(up);CLEAR_REG(rght);
}
inline void Build(){
for (long long i=0;i<n;i++)
for (long long j=m-1;j>=0;j--) if (a[i][j]=='.'){
up[i][j]=i==0?0:up[i-1][j]+1;
rght[i][j]=rght[i][j+1]+1;
} else up[i][j]=rght[i][j]=-1;
}
long long TwoLLogo::countWays(vector <string> grid) {
init();a=grid;
n=grid.size();m=grid[0].length();
Build();
for (long long i=0;i<n;i++)
for (long long j=0;j<m;j++) if (a[i][j]=='.')
for (long long k=0;k<n;k++)
for (long long t=0;t<m;t++) if ((a[k][t]=='.')&&((i!=k)||(j!=t))){
if ((up[i][j]==0)||(rght[i][j]==0)||(up[k][t]==0)||(rght[k][t]==0)) continue;
if ((i<k)&&(j>t)) ans+=rght[i][j]*up[i][j]*rght[k][t]*up[k][t]; else
if ((i<k)&&(j<t)) ans+=max((long long)0,
up[i][j]*rght[i][j]*min(up[k][t],k-i-1)*rght[k][t]+
up[i][j]*min(rght[i][j],t-j-1)*up[k][t]*rght[k][t]-
up[i][j]*min(up[k][t],k-i-1)*min(rght[i][j],t-j-1)*rght[k][t]); else
if ((i<k)&&(j==t)) ans+=up[i][j]*rght[i][j]*min(up[k][t],k-i-1)*rght[k][t];
if ((i==k)&&(j<t)) ans+=up[i][j]*up[k][t]*min(rght[i][j],t-j-1)*rght[k][t];
}
return ans;
}


• 默认
• 护眼
• 夜晚
• Serif
• Sans