Fm.java

/*
 * CTU Open 2013
 * HES
 */
package template;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
/**
 *
 * @author cteam007
 */
public class Fm {
 
    StringTokenizer st = new StringTokenizer("");
    BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
 
    void useLine(String s) {
        st = new StringTokenizer(s);
    }
 
    String nextToken() throws Exception {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(input.readLine());
        }
        return st.nextToken();
    }
 
    int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }
 
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws Exception {
        Fm instance = new Fm();
        while (instance.run()) {
        }
    }
 
    boolean run() throws Exception {
        String in = input.readLine();
        if (in == null) {
            return false;
        }
 
        useLine(in);
 
        int rows = nextInt();
        int cols = nextInt();
 
        int tileRows = nextInt();
        int tileCols = nextInt();
 
        String[] map = new String[rows * 3];
 
        String rowAddon = "";
        String colAddon = "";
 
        for (int ra = 0; ra < cols; ra++) {
            rowAddon += ".";
        }
 
        for (int ra = 0; ra < cols * 3; ra++) {
            colAddon += ".";
        }
 
        for (int i = 0; i < rows; i++) {
            map[i] = colAddon;
        }
 
        for (int i = rows; i < rows * 2; i++) {
            map[i] = rowAddon + nextToken() + rowAddon;
        }
 
        for (int i = rows*2; i < rows*3; i++) {
            map[i] = colAddon;
        }
 
        /*
        System.out.println("");
        for(int i = 0; i < rows*3 ; i++){
            System.out.println(map[i]);
        }   
        System.out.println("");
         * */
 
        TileStructure ts = new TileStructure(rows, cols, tileRows, tileCols, map);
 
        int min = Integer.MAX_VALUE;
 
        for (int i = 0; i < tileRows; i++) {
            for (int j = 0; j < tileCols; j++) {
                //System.out.println("Iteration[" + (-i) + "," + (-j) + "]");
                min = Math.min(min,ts.getNumber(-i, -j));
            }
        }
 
        System.out.println(min);
 
        return true;
    }
}
 
class TileStructure {
 
    int tilesH;
    int tilesW;
    int tileRows;
    int tileCols;
    int cols;
    int rows;
    String[] map;
 
    public TileStructure(int rows, int cols, int tileRows, int tileCols, String[] map) {
        tilesH = rows / tileRows + ((rows % tileRows == 0) ? (0) : (1)) + 1;
        tilesW = cols / tileCols + ((cols % tileCols == 0) ? (0) : (1)) + 1;
 
        this.tileCols = tileCols;
        this.tileRows = tileRows;
        this.map = map;
 
        this.cols = cols;
        this.rows = rows;
    }
 
    public int getNumber(int xOffset, int yOffset) {
        int count = 0;
 
        for (int h = 0; h < tilesH; h++) {
            for (int w = 0; w < tilesW; w++) {
                boolean hasX = false;
                for (int ht = h * tileRows; ht < h * tileRows + tileRows && !hasX; ht++) {
                    for (int wt = w * tileCols; wt < w * tileCols + tileCols && !hasX; wt++) {
                        //System.out.print("T[" + h + "," + w + "]-[" + (ht+rows) + "," + (wt+cols) + "] = ");
                        if (map[ht+rows+xOffset].charAt(wt+cols+yOffset) == 'X') {
                            hasX = true;
                        }
                            //System.out.println("X");
                        //}else{
                            //System.out.println(".");
                        //}
                    }
                }
                if (hasX) {
                    count++;
                }
            }
        }
 
        return count;
    }
}