2019 우 객 다 교 8 차 전 - A. All - one Matrices [단조 로 운 스 택 / 사고] [확대 할 수 없 는 전체 1 자 행렬 개수]

링크:https://ac.nowcoder.com/acm/contest/888/A
제목 설명
Gromah and LZR entered the great tomb, the first thing they see is a matrix of size n×mn\times mn×m, and the elements in the matrix are all 00_{}0​ or 11_{}1​.
LZR finds a note board saying "An all-one matrix is defined as the matrix whose elements are all 11_{}1​, you should determine the number of all-one submatrices of the given matrix that are not completely included by any other all-one submatrices".
Meanwhile, Gromah also finds a password lock, obviously the password should be the number mentioned in the note board!
Please help them determine the password and enter the next level.
입력 설명:
The first line contains two positive integers n,mn,m_{}n,m​, denoting the size of given matrix.
Following nn_{}n​ lines each contains a string with length mm_{}m​, whose elements are all 00_{}0​ or 11_{}1​, denoting the given matrix.
1≤n,m≤30001\le n,m \le 30001≤n,m≤3000
출력 설명:

Print a non-negative integer, denoting the answer.

입력

3 4
0111
1110
0101

출력

5

설명 하 다.

The 5 matrices are (1,2)−(1,4),  (1,2)−(2,3),  (1,2)−(3,2),  (2,1)−(2,3),  (3,4)−(3,4)(1,2)-(1,4), \; (1,2)-(2,3), \; (1,2)-(3,2), \; (2,1)-(2,3), \; (3,4)-(3,4)_{}(1,2)−(1,4),(1,2)−(2,3),(1,2)−(3,2),(2,1)−(2,3),(3,4)−(3,4)​.

제목:
01 행렬 을 드 리 겠 습 니 다. 확대 할 수 없 는 모든 1 행렬 의 개 수 를 구 합 니 다.
분석:
각각 [i, j] 에 대해 서 는 그것 부터 위로 연속 되 는 1 의 숫자 num 을 기록 합 니 다.
매 줄 마다 행렬 의 밑변 에 익숙 합 니 다. 이전 에는 각 열 을 뒤로 매 거 하여 num 이 단 조 롭 게 상승 하 는 스 택 을 유지 하고 스 택 의 모든 num 값 에 대해 서 는 이 num 의 대응 위치 가 왼쪽으로 가장 멀리 확장 할 수 있 는 위치 pos 를 유지 해 야 합 니 다.
요소 가 스 택 에서 나 올 때 이 요 소 를 (num, pos) 로 설정 하면 전체 1 행렬 (i - num + 1, pos) - > (i, j) 을 얻 을 수 있 습 니 다.
이때 이 행렬 의 가장 왼쪽 은 pos 로 기록 되 어 있 습 니 다 (왼쪽으로 확장 할 수 없습니다). 위로 최대 num 으로 기록 되 어 있 습 니 다 (위로 확장 할 수 없습니다). 현재 num 보다 크 기 때문에 스 택 (오른쪽으로 확장 할 수 없습니다) 을 나 올 수 있 습 니 다. 아래로 확장 할 수 있 는 지 판단 하면 안 된다 면 이것 이 답 행렬 입 니 다.

#include
using namespace std;
const int maxn=3007;
char s[maxn][maxn];
int num[maxn][maxn];
stack< pair > S;
int main()
{
	int n,m;scanf("%d%d",&n,&m);getchar();
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++) scanf("%c",&s[i][j]);
		getchar();
	}
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			num[i][j]=(s[i][j]=='1')?num[i-1][j]+1:0;
	int ans=0;
    for (int i=1;i<=n;i++)
    {
    	int tmp=-1;
    	while (!S.empty()) S.pop();
    	for (int j=1;j<=m+1;j++)
    	{
    		int pos=j;
    		while (!S.empty() && S.top().first>num[i][j])
	    	{
	    		if(S.top().second<=tmp) ans++;//    [pos,j]  0         
	    		pos=S.top().second;
	    		S.pop();
	    	}
	    	if(!num[i+1][j]) tmp=j;//             0   
	    	if(num[i][j] && (S.empty() || S.top().first