Right Triangles

2024-08-27 23:18

文章标签 triangles right

本文主要是介绍Right Triangles，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

H - Right Triangles

Time Limit:2000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u

Submit Status Practice CodeForces 52B

Description

You are given a n × m field consisting only of periods ('.') and asterisks ('*'). Your task is to count all right triangles with two sides parallel to the square sides, whose vertices are in the centers of '*'-cells. A right triangle is a triangle in which one angle is a right angle (that is, a 90 degree angle).

Input

The first line contains two positive integer numbers n and m (1 ≤ n, m ≤ 1000). The following n lines consist of m characters each, describing the field. Only '.' and '*' are allowed.

Output

Output a single number — total number of square triangles in the field. Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

Sample Input

Input

2 2
**
*.

Output

Input

3 4
*..*
.**.
*.**

Output

#include<stdio.h>
#include<string.h> 
int main()
{int n,m,i,j,r[1011],c[1011];__int64 s,t;char a[1011][1011];while(~scanf("%d%d",&n,&m)){s=t=0;memset(r,0,sizeof(r));memset(c,0,sizeof(c));for(i=0;i<n;i++){scanf("%s",a[i]);for(j=0;j<m;j++)if(a[i][j]=='*'){r[i]++;c[j]++;}}for(i=0;i<n;i++){s=0;for(j=0;j<m;j++)if(a[i][j]=='*')s+=c[j]-1;t+=s*(r[i]-1);}printf("%I64d\n",t);}
}

这篇关于Right Triangles的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

原文地址:
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.chinasem.cn/article/1113066。如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈，一经查实，立即删除！我们的邮箱：23002807@qq.com