TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4271
  • Problem
  • P4271小奇的矩阵
    Limits : Time Limit : - MS   Memory Limit : 265536 KB
    Judgment Tips : 1s
    Description

    【题目背景】

    小奇总是在数学课上思考奇怪的问题。

     

    【问题描述】

    给定一个n*m的矩阵,矩阵中的每个元素aij为正整数。

    接下来规定

    1.合法的路径初始从矩阵左上角出发,每次只能向右或向下走,终点为右下角。

    2.路径经过的n+m-1个格子中的元素为A1,A2…A(n+m-1),Aavg为Ai的平均数,路径的V值为(n+m-1)*∑(Ai-Aavg) ^2

    (1<=i<=n+m-1)

    求V值最小的合法路径,输出V值即可,有多组测试数据。

    Input Format

    第一行包含一个正整数T,表示数据组数。

    对于每组数据:

    第一行包含两个正整数n和m,表示矩阵的行数和列数。
    接下来n行,每行m个正整数aij,描述这个矩阵。

    Output Format

    对于每次询问,输出一行一个整数表示要求的结果

    Sample Input

    1
    2 2
    1 2
    3 4

    Sample Output

    14

    Hint

    对于30%的数据 n<=10,m<=10

    有另外40%的数据 n<=15 m<=15,矩阵中的元素不大于5

    对于100%的数据 T<=5,n<=30,m<=30,矩阵中的元素不大于30


    Source  hzwer