【题目】

原文：

1.7 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.

译文：

写一个函数处理一个MxN的矩阵，如果矩阵中某个元素为0，那么把它所在的行和列都置为0.

【分析】

【思路一】

遍历一次矩阵，当遇到元素等于0时，记录下这个元素对应的行和列。 可以开一个行数组row和列数组col，当元素a[i][j]等于0时， 就把row[i]和col[j]置为true。第二次遍历矩阵时，当某个元素对应的行row[i] 或列col[j]被设置为true，说明该元素在需要被置0的行或列上，因此将它置0。

【思路二】

想要常数空间，可以复用第一行和第一列作为辅助空间使用。不用开辟新的存储空间。其实第一行和第一列所在数组就是思路1中设置的数组，这样减少空间开销。
1.先确定第一行和第一列是否需要清零即，看看第一行中是否有0，记下来。也同时记下来第一列中有没有0。
2.扫描剩下的矩阵元素，如果遇到了0，就将该行第一个元素和该列第一个元素赋值为0即赋值第一行数组和第一列数组。
这里不用担心会将本来第一行或第一列的1改成了0，因为这些值最后注定要成为0的。
3.根据第一行和第一列的信息，已经可以将剩下的矩阵元素赋值为结果所需的值了即，拿第一行为例，如果扫描到一个0，就将这一列都清0。
4.根据1中确定的状态，处理第一行和第一列。如果最开始得到的第一行中有0的话，就整行清零。同理对列进行处理。

【代码一】

/*********************************
*   日期：2014-05-15
*   作者：SJF0115
*   题目:  Set Matrix Zeroes
*   来源：CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

void  SetMatrixZeroes(int **matrix,int m,int n){
    int i,j;
    //初始化
    int* col = new int(n+1);
    int* row = new int(m+1);
    memset(col,0,sizeof(int)*(n+1));
    memset(row,0,sizeof(int)*(m+1));
    //寻找0
    for(i = 0;i < m;i++){
        for(j = 0;j < n;j++){
            if(matrix[i][j] == 0){
                row[i] = col[j] = 1;
            }//if
        }//for
    }//for
    //0所在列和行全置为0
    for(i = 0;i < m;i++){
        for(j = 0;j < n;j++){
            if(row[i] || col[j]){
                matrix[i][j] = 0;
            }//if
        }//for
    }//for
}

int main(){
    int m,n,i,j;
    //freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
    while(scanf("%d%d",&m,&n) != EOF){
        if(m == 0 || n == 0){
            break;
        }
        //初始化
        int** matrix = new int*[m];
        for(i = 0;i < m;i++){
            matrix[i] = new int[n];
        }
        //输入
        for(i = 0;i < m;i++){
            for(j = 0;j < n;j++){
                cin>>matrix[i][j];
            }
        }
        //置0
        SetMatrixZeroes(matrix,m,n);
        //输出
        for(i = 0;i < m;i++){
            for(j = 0;j < n;j++){
                cout<<matrix[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    return 0;
}

【代码二】

/*********************************
*   日期：2014-05-15
*   作者：SJF0115
*   题目: Set Matrix Zeroes
*   来源：CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
//Set Matrix Zeroes
void  SetMatrixZeroes(int **matrix,int m,int n){
    int i,j;
    int firstRow = 0;
    int firstCol = 0;
    //判断第一行是否有0
    for(i = 0;i < n;i++){
        if(matrix[0][i] == 0){
            firstRow = 1;
        }
    }//for
    //判断第一列是否有0
    for(i = 0;i < m;i++){
        if(matrix[i][0] == 0){
            firstCol = 1;
        }
    }//for
    //搜索0进行标记
    for(i = 0;i < m;i++){
        for(j = 0;j < n;j++){
            if(matrix[i][j] == 0){
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }//if
        }//for
    }//for
    //根据第一行和第一列把剩余元素进行置零
    for(i = 1;i < m;i++){
        for(j = 1;j < n;j++){
            if(matrix[i][0] == 0 || matrix[0][j] == 0){
                matrix[i][j] = 0;
            }//if
        }//for
    }//for
    //第一行存有0则全设置为0
    if(firstRow){
        for(i = 0;i < n;i++){
            matrix[0][i] = 0;
        }
    }//if
    //第一列存有0则全设置为0
    if(firstCol){
        for(i = 0;i < m;i++){
            matrix[i][0] = 0;
        }
    }//if
}

int main(){
    int m,n,i,j;
    freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
    while(scanf("%d%d",&m,&n) != EOF){
        if(m == 0 || n == 0){
            break;
        }
        //初始化
        int** matrix = new int*[m];
        for(i = 0;i < m;i++){
            matrix[i] = new int[n];
        }
        //输入
        for(i = 0;i < m;i++){
            for(j = 0;j < n;j++){
                cin>>matrix[i][j];
            }
        }
        //置0
        SetMatrixZeroes(matrix,m,n);
        //输出
        for(i = 0;i < m;i++){
            for(j = 0;j < n;j++){
                cout<<matrix[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    return 0;
}