読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 544 Div1 Medium: FlipGame

SRM 競技プログラミング

解法

貪欲にやれば良い。

コード

public class FlipGame {

	public int minOperations(String[] strings) {
		int N = strings.length;
		char[][] board = new char[N][];
		for (int i = 0; i < N; i++) {
			board[i] = strings[i].toCharArray();
		}
		int M = board[0].length;

		int turn = 0;
		while (true) {
			boolean finish = true;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (board[i][j] == '1') {
						finish = false;
					}
				}
			}
			if (finish) {
				return turn;
			}

			turn++;
			int now = -1;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (board[i][j] == '1') {
						now = Math.max(now, j);
					}
				}

				for (int j = 0; j <= now; j++) {
					if (board[i][j] == '1') {
						board[i][j] = '0';
					} else {
						board[i][j] = '1';
					}
				}
			}
		}
	}

}