データ構造 〜 第1章 配列と文字列 問題1-7

世界で闘うプログラミング力を鍛える150問 ~トップIT企業のプログラマになるための本~

問題1-7.

M×Nの行列について、要素が0であれば、その行とその列の全てを0にするアルゴリズムを作成する。

考え中。

記載された解答の考え方と同じ。
だけど、最初は添字だけで考えておらず、行列の要素を0にしようと考えていた。

package solve;

public class Solve {

	public static void main(String[] args) {
		if(args.length == 0){
			System.out.println("行列のサイズを入力してください。");
			return;
		}
		
		int M = Integer.parseInt(args[0]);
		int N = Integer.parseInt(args[1]);
		int[][] matrix = new int[M][N];
		
		//元の長方形の作成
		for(int m=0; m<M; ++m){
			for(int n=0; n<N; ++n){
				matrix[m][n] = ((m == 2 && n == 2) ? 0 : 1);
				System.out.print(matrix[m][n]);
			}
			System.out.println();
		}
		System.out.println();
		
		Solve solve = new Solve();
		matrix = solve.solve(matrix);
		
		for(int m=0; m<M; ++m){
			for(int n=0; n<N; ++n){
				System.out.print(matrix[m][n]);
			}
			System.out.println();
		}
		System.out.println();
	}
	
	/**
	 * 長方形の要素が0の行、列を0で埋める。
	 * @param matrix
	 * @return
	 */
	public int[][] solve(int[][] matrix){
		if(matrix.length == 0){
			return null;
		}
		
		if(matrix[0].length == 0){
			return null;
		}
		
		int M 			  =  matrix.length;    //長方形の縦の長さ
		int N 			  =  matrix[0].length; //長方形の横の長さ
		boolean[] row = new boolean[M];
		boolean[] col = new boolean[N];
		
		/**
		 * 長方形の要素が0になる添字を記憶する。
		 */
		for(int m=0; m<M; ++m){
			for(int n=0; n<N; ++n){
				if(matrix[m][n] == 0){
					row[m] = true;
					col[n] = true;
				}
			}
		}
		
		for(int m=0; m<M; ++m){
			for(int n=0; n<N; ++n){
				if(row[m] == true || col[n] == true){
					matrix[m][n] = 0;
				}
			}
		}
		
		return matrix;
	}
}