Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

重点是空间复杂度限制为常数．

人家想法：

用 matrix 的第０行和第０列的元素分别记录所对应的行和列是否有０．

A[0][0]比较特殊，我们只让它记录第０行的情况，声明另一变量col0记录第0列的情况．

我的实现代码较长，但思路表达的相当清楚．人家也有贼短的代码，人家很牛逼．

算法分两大阶段(细分为 ８ steps, 在程序注释中所示)

1. 设置第０行，第０列以及col0，让它们正确表达所对应行、列的状态；
2. 依据上述状态将对应行、列置０．

第一第二阶段均需注意顺序，如程序中注释所示．

第二阶段清０时，如下图：

^ 表示第０行或第０列的元素;

* 表示非０行，非０列元素

依据状态置0时，先清非第0行和第0列的元素，那就是 * 表示的那帮货！

再清第0行，最后依据col0清第0列．

^ ^ ^

^ * *

^ * *

有意思的是：col0展示了她的重要地位，她已跳出三界外，不在五行中．整个程序从她而起，最后又由她而终！

自己代码和注释:

\(O(n^2)\) time, \(O(1)\) space.

void setZeroes(vector<vector<int>>& A) {

	// 程序分为8个step, 各step顺序不能颠倒

	// 终极目的是避免记录状态的第0行和第0列被误写

	int m = A.size(), n = A[0].size(), col0 = 1;

	// step1. 若第0列有0, col0 = 0

	for (int i = 0; i < m; i++)

		if (A[i][0] == 0) {

			col0 = 0;

			break;

		}

	// step2. 若第0行有0, row0 = 0

	for (int j = 0; j < n; j++)

		if (A[0][j] == 0) {

			A[0][0] = 0;

			break;

		}

	// step3. 依次检查除第0列以外的其他列j,若那列有0,则A[0][j]=0

	for (int j = 1; j < n; j++)

		for (int i = 0; i < m; i++)

			if (A[i][j] == 0) {

				A[0][j] = 0;

				break;

			}

	// step4. 依次检查除第0行以外的其他行i,若那行有0,则A[i][0]=0

	for (int i = 1; i < m; i++)

		for (int j = 0; j < n; j++)

			if (A[i][j] == 0) {

				A[i][0] = 0;

				break;

			}

	// 阶段性胜利：到此为止，我们把第0行与第0列，以及col0的 state 设置完成了

	// 接下来，我们要根据上述状态，将对应元素设置为0

	// step5. 依据第0列，修改第1~(m-1)行元素为0(注意：不改第0行，因为那里存着state)

	for (int i = 1; i < m; i++)

		if (A[i][0] == 0)

			for (int j = 1; j < n; j++)

				A[i][j] = 0;

	// step6. 依据第0行，修改第1~(n-1)列元素为0(注意：不改第0列，因为那里存着state)

	for (int j = 1; j < n; j++)

		if (A[0][j] == 0)

			for (int i = 1; i < m; i++)

				A[i][j] = 0;

	// step7. 按照A[0][0], 修改第0行元素为0

	if (A[0][0] == 0)

		for (int j = 1; j < n; j++)

			A[0][j] = 0;

	// step8. 按照col0, 修改第0列元素为0, 再次强调, 以上次序不能调换

	if (col0 == 0)

		for (int i = 0; i < m; i++) //此时需将A[0][0]元素包含在内

			A[i][0] = 0;

}