边数

Question

给你一个网格；具有n行；和m列；其中两个单元格被称为相邻的，如果：它们有一个公共边。

设两个相邻单元格为A和B。因为它们是相邻的；因此；您可以从A转到B；以及从B到A。

从图论的角度；我们可以说，如果网格被建模为有向图；则存在从a到B的有向边；以及A从B到；如果单元格A和B相邻。

要求你找出图中有向边的数目。

输入格式

输入的第一行包含单个整数T；表示测试用例的数量。

然后；t行紧随其后；其中每行包含两个空格分隔的整数n和m；网格的尺寸。

采样输入0

1
3 3

示例输出0

24

解释%0

有向边数为24。

这种做法是否正确？我的代码确实通过了示例测试用例，但对其他测试用例却失败了

def compute(m,n):
 arr = [[0 for x in range(n)] for y in range(m)] 
 arr[0][0]=2
 arr[n-1][m-1]=2
 arr[0][m-1]=2
 arr[n-1][0]=2
 for i in range (1,m-1):
     arr[i][0]=3
     arr[i][n-1]=3
 for j in range (1,n-1):
     arr[0][j]=3
     arr[n-1][j]=3
 for i in range (1,n-2):
     for j in range (1,m-2):
         arr[i][j]=4
 return sum(sum(arr,[])) +4 

请解释解决此问题的正确方法。谢谢

Answer 1

你可以找到一个计算图中边数的公式如下：假设我们有一个尺寸为n和m的网格。对于每个单元，我们需要计算相邻单元的数量。那么，这类数字的总和就是边的个数。

情况1）这样的网格具有4个角单元，每个角单元具有2个邻居；总邻居情况1:4*2=8

情况2：这样的网格在其边具有2(n+m-2)-4个单元格（不包括每个具有3个邻居的角），总邻居情况2:(2(n+m-2)-4)3

情况3）这样的网格具有nm-(2(n+m-2)-4)-4个内单元，每个内单元具有4个邻居，总邻居情况3:*(nm-(2(n+m-2)-4)-4)4

边总数=情况1+情况2+情况3=8+(2(n+m-2)-4)3+(nm-(2(n+m-2)-4)-4)4=4nm-2(n+m)

因此您可以使用下面的代码来计算边数：

def compute_total_edges(m,n):
    return 4*n*m-2*(n+m)

print(compute_total_edges(3,3))