矩阵归零消减序列和 总时间限制: 1000ms 内存限制: 65536kB 描述 给定一个n*n的矩阵（3 <= n <= 100，元素的值都是非负整数）。通过n-1次实施下述过程，可把这个矩阵转换成一个1*1的矩阵。每次的过程如下： 首先对矩阵进行行归零：即对每一行上的所有元素，都在其原来值的基础上减去该行上的最小值，保证相减后的值仍然是非负整数，且这一行上至少有一个元素的值为0。 接着对矩阵进行列归零：即对每一列上的所有元素，都在其原来值的基础上减去该列上的最小值，保证相减后的值仍然是非负整数，且这一列上至少有一个元素的值为0。 然后对矩阵进行消减：即把n*n矩阵的第二行和第二列删除（如果二维数组为a[][]，则删除的是a[1][1]所在的行和列），使之转换为一个(n-1)*(n-1)的矩阵。 下一次过程，对生成的(n-1)*(n-1)矩阵实施上述过程。显然，经过n-1次上述过程， n*n的矩阵会被转换为一个1*1的矩阵。 请求出每次消减前a[1][1]值之和。 输入 第一行是一个整数n。 其后是n个n*n的矩阵。 每个矩阵占n行，每行有n个正整数，每个整数间用空格分隔。 输出 输出为n行，每行上的整数为对应矩阵归零消减过程中，每次消减前a[1][1]值之和。 样例输入 3 1 2 3 2 3 4 3 4 5 1 2 3 5 4 2 9 4 5 1 2 3 5 4 2 9 5 4 样例输出 0 2 1
提示：
请比较两种做法！
第一种做法得到的结果不正确,第二种才是正确的。
其实就是说：归零时先按行归零，再按列归零。
对每一行或每一列归零时，扫描行或列，假如里面含0，那这一行或列的归零工作就免了，直接处理下一行或列。
1 #include<stdio.h> 2 int main() 3 { 4 int a[100][100],i,j,k,n; 5 int rowMin,colMin; 6 int x; 7 int sum; 8 freopen("5.in","r",stdin); 9 freopen("result.out","w",stdout); 10 scanf("%d",&n); 11 for(k=0;k<n;k++) 12 { 13 //输入二维数组 14 for(i=0;i<n;i++) 15 { 16 for(j=0;j<n;j++) 17 { 18 scanf("%d",&a[i][j]); 19 } 20 } 21 sum=0; 22 //归零和消减，整个操作有n-1次，每次进行时数组的阶是x 23 for(x=n;x>1;x--) 24 { 25 //行的归零 26 for(i=0;i<x;i++) 27 { 28 rowMin=a[i][0]; 29 for(j=1;j<x&&rowMin>0;j++) 30 { 31 if(a[i][j]<rowMin) 32 { 33 rowMin=a[i][j]; 34 } 35 } 36 if(rowMin!=0) 37 { 38 for(j=0;j<x;j++) 39 { 40 a[i][j]=a[i][j]-rowMin; 41 } 42 } 43 44 } 45 //列的归零 46 for(j=0;j<x;j++) 47 { 48 colMin=a[0][j]; 49 for(i=1;i<x&&colMin>0;i++) 50 { 51 if(a[i][j]<colMin) 52 { 53 colMin=a[i][j]; 54 } 55 } 56 if(colMin!=0) 57 { 58 for(i=0;i<x;i++) 59 { 60 a[i][j]=a[i][j]-colMin; 61 } 62 } 63 } 64 sum=sum+a[1][1]; 65 //下面是消减 66 i=0; 67 for(j=2;j<x;j++) 68 a[i][j-1]=a[i][j]; 69 j=0; 70 for(i=2;i<x;i++) 71 a[i-1][j]=a[i][j]; 72 for(i=2;i<x;i++) 73 { 74 for(j=2;j<x;j++) 75 { 76 a[i-1][j-1]=a[i][j]; 77 } 78 } 79 } 80 printf("%d\n",sum); 81 } 82 return 0; 83 }
