曼哈顿距离

　

曼哈顿距离

Problem:曼哈顿距离

Description:

在平面上，坐标（x1, y1）的点P1与坐标（x2, y2）的点P2的曼哈顿距离为：|x1-x2|+|y1-y2|。 现在有一个nXn (1<=n<=1000)的矩阵，一开始矩阵中每个元素的值都为零。 对这个矩阵进行m (1<=m<=100000)次操作，每次操作定义如下：

(x1, y1), (x2, y2): 对于矩阵中满足x1<=x<=x2, y1<=y<=y2的所有元素(x, y)加上(x, y)与(x1, y1)的曼哈顿距离|x1-x|+|y1-y|

例如，当n=5，m=2，两组操作分别为(1, 1), (4, 4)和(2, 2), (5, 5):

现在想让你输出m次操作后的矩阵，但是由于本OJ输出文件不能超过1M，所以输出矩阵所有非零元素的乘积即可 （结果对1000000007取余）,没有非零项则输出0；

Input:

第一行两个整数n， m，分别表示正方形网格的边长和操作次数；

接下来m行，每行4个整数x1 y1 x2 y2；

Output:

输出一个整数代表答案。

Sample Input:

5 2

1 1 4 4

2 2 5 5

Sample Output:

853543927

Language:C++

#include <iOStream>
#include <cstring>

using namespace std;

const int N=1010;
const int mod=1e9+7;

int sum[N][N],tot[N][N];

int main()
{
  int n,m;
  cin>>n>>m;
  memset(sum,0,sizeof(sum));
  memset(tot,0,sizeof(tot));

  while(m--)
  {
    int up,left,down,right;
    cin>>up>>left>>down>>right;

    sum[up][left]+=up+left;
    sum[up][right+1]-=up+left;
    sum[down+1][left]-=up+left;
    sum[down+1][right+1]+=up+left;

    tot[up][left]++;
    tot[up][right+1]--;
    tot[down+1][left]--;
    tot[down+1][right+1]++;
  }

  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=n;j++)
    {
      sum[i][j]+=sum[i][j-1];
      tot[i][j]+=tot[i][j-1];
    }
  }

  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=n;j++)
    {
      sum[i][j]+=sum[i-1][j];
      tot[i][j]+=tot[i-1][j];
    }
  }

  long long ans=1,number=0;
  bool flag=false;
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=n;j++)
    {
      number=tot[i][j]*(i+j)-sum[i][j];
      if(number)
      {
        ans=ans*number%mod;
        flag=true;
      }
    }
  }

  if(flag) cout<<ans<<endl;
  else cout<<0<<endl;

  return 0;
}

文章最后发布于: 2018-12-09 23:34:08

相关阅读

点到直线的距离公式

然后

球坐标系下的两点距离公式

https://blog.csdn.net/yu412346928/article/details/42966001 已知两点经纬度计算球面距离的公式，一搜一大堆，形式如下： 可是至于

曼哈顿距离和切比雪夫距离

转载 https://www.cnblogs.com/zwfymqz/p/8253530.html 本文只讨论二维空间中的曼哈顿距离与切比雪夫距离 曼哈顿距离 定义

PHP 通过经纬度计算距离

传递参数：地址1的纬度：$lat1  ，经度：$lng1，地址2的纬度   $lat2  ，经度：$lng2，示例：封装的方法：/** * 计算两个经纬度距离 */

关于曼哈顿距离和切比雪夫距离

【感谢xly苣铑】 【曼哈顿距离】 【切比雪夫距离】 【关于两者的关系】 距离原点曼哈顿距离为d的点集如下图：它们在红色的