USACO 2017 January Contest, Bronze Problem 3. Cow Tipping

原题下载

USACO2017-JAN-B3

答案:

import java.io.*;
import java.util.*;
public class cowtip {
public static void main(String[] args) throws IOException {
// initialize file I/O
BufferedReader br = new BufferedReader(new FileReader("cowtip.in"));
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("cowtip.out")));

// read in the size of the grid
int n = Integer.parseInt(br.readLine());

// allocate a 2D array for the grid
char[][] grid = new char[n][n];

// define constants to indicate which squares are correct
final char WRONG = '1';
final char RIGHT = '0';

// read in the grid
for(int i = 0; i < n; i++) {
// read in a row of the grid
String s = br.readLine();
for(int j = 0; j < n; j++) {
// update the relevant row in the array
grid[i][j] = s.charAt(j);
}
}

int numTips = 0;
// loop over the rectangles to consider from bottom to top, right to left
for(int i = n-1; i >= 0; i--) {
for(int j = n-1; j >= 0; j--) {
if(grid[i][j] == WRONG) {
// the rectangles with bottom-right corner at (i, j) needs to be toggled
numTips++;
for(int a = 0; a <= i; a++) {
for(int b = 0; b <= j; b++) {
// flip each entry in that rectangle
if(grid[a][b] == WRONG) {
grid[a][b] = RIGHT;
}
else {
grid[a][b] = WRONG;
}
}
}
}
}
}

// print the answer
pw.println(numTips);

// close the file
pw.close();
}
}