1207 B. Square Filling
16 March 2025
[ algorithms , codeforces , greedy ]

Give this problem a try 1207 B. Square Filling.


Approach


Example Code

import java.io.*;
import java.util.*;

public class Solution {
    public static void main(String[] args) throws Exception {
        // FastScanner io = new FastScanner("");
		FastScanner io = new FastScanner();

		int t = 1; // t = io.nextInt();
		while (t > 0) {
			int n = io.nextInt(), m = io.nextInt();
			
			int[][] A = new int[n][m];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					A[i][j] = io.nextInt();
				}
			}

			// greedy choose squares
			List<int[]> chosen = new ArrayList<>();
			for (int i = 0; i < n-1; i++) {
				for (int j = 0; j < m-1; j++) {
					if (A[i][j] * A[i+1][j] * A[i][j+1] * A[i+1][j+1] > 0) {
						A[i][j] = 2;
						A[i+1][j] = 2;
						A[i][j+1] = 2;
						A[i+1][j+1] = 2;
						chosen.add(new int[]{i,j});
					}
				}
			}

			// check if any 1 is unfilled
			int cnt = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (A[i][j] == 1) cnt++;
				}
			}

			if (cnt > 0) {
				io.println(-1);
				t--; continue;
			}
			
			io.println(chosen.size());
			for (int i = 0; i < chosen.size(); i++) {
				int[] p = chosen.get(i);
				io.println((p[0]+1) + " " + (p[1]+1));
			}

			t--;
		}

		io.close();
    }

    /**
        RESERVED NUMBERS
    */
    public static int MOD = 1_000_000_007; // prime number
	public static int INF = 1_000_000_007; // infinity number

    /**
        DATA STRUCTURES
    */
    static class MultiSet {
        static TreeMap<Integer, Integer> multiset;
		public MultiSet() { multiset = new TreeMap<>(); }
        static void add(int x) {
            multiset.putIfAbsent(x, 0);
            multiset.put(x, multiset.get(x)+1);
        }
        static void remove(int x) {
            multiset.putIfAbsent(x, 0);
            multiset.put(x, multiset.get(x)-1);
            if (multiset.get(x) <= 0) multiset.remove(x);
        }
    }

    /**
        IO
    */
    static class FastScanner extends PrintWriter {
        private BufferedReader br;
        private StringTokenizer st;
		
		// standard input
        public FastScanner() { this(System.in, System.out); }
		public FastScanner(InputStream i, OutputStream o) {
            super(o);
			st = new StringTokenizer("");
            br = new BufferedReader(new InputStreamReader(i));
        }
		// USACO-style file input
        public FastScanner(String problemName) throws IOException {
            super(problemName + ".out");
			st = new StringTokenizer("");
            br = new BufferedReader(new FileReader(problemName + ".in"));
        }

        // returns null if no more input
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(br.readLine());
                return st.nextToken();
            } catch (Exception e) { }
            return null;
        }
        public int nextInt() { return Integer.parseInt(next()); }  
        public double nextDouble() { return Double.parseDouble(next()); }   
        public long nextLong() { return Long.parseLong(next()); }   
    }
}

Complexity Analysis

  • Time Complexity: $O(N \times M)$
  • Space Complexity: $O(N \times M)$

Sign-off

Congratulations on making it this far! Best of luck in your future competitions!