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!