1591. Strange Printer II

There is a strange printer with the following two special requirements:

  • On each turn, the printer will print a solid rectangular pattern of a single color on the grid. This will cover up the existing colors in the rectangle.
  • Once the printer has used a color for the above operation, the same color cannot be used again.

You are given a m x n matrix targetGrid, where targetGrid[row][col] is the color in the position (row, col) of the grid.

Return true if it is possible to print the matrix targetGrid, otherwise, return false.

 

Example 1:

Input: targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
Output: true

Example 2:

Input: targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
Output: true

Example 3:

Input: targetGrid = [[1,2,1],[2,1,2],[1,2,1]]
Output: false
Explanation: It is impossible to form targetGrid because it is not allowed to print the same color in different turns.

Example 4:

Input: targetGrid = [[1,1,1],[3,1,3]]
Output: false

 

Constraints:

  • m == targetGrid.length
  • n == targetGrid[i].length
  • 1 <= m, n <= 60
  • 1 <= targetGrid[row][col] <= 60

Rust Solution

struct Solution;

use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::VecDeque;

impl Solution {
    fn is_printable(target_grid: Vec<Vec<i32>>) -> bool {
        let n = target_grid.len();
        let m = target_grid[0].len();
        let mut color: HashMap<i32, usize> = HashMap::new();
        for i in 0..n {
            for j in 0..m {
                let size = color.len();
                color.entry(target_grid[i][j]).or_insert(size);
            }
        }
        let c = color.len();
        let mut left: Vec<usize> = vec![m - 1; c];
        let mut right: Vec<usize> = vec![0; c];
        let mut top: Vec<usize> = vec![n - 1; c];
        let mut bottom: Vec<usize> = vec![0; c];
        for i in 0..n {
            for j in 0..m {
                let u = color[&target_grid[i][j]];
                left[u] = left[u].min(j);
                right[u] = right[u].max(j);
                top[u] = top[u].min(i);
                bottom[u] = bottom[u].max(i);
            }
        }
        let mut adj: Vec<HashSet<usize>> = vec![HashSet::new(); c];
        for i in 0..n {
            for j in 0..m {
                let u = color[&target_grid[i][j]];
                for v in 0..c {
                    if v == u {
                        continue;
                    }
                    if left[v] <= j && j <= right[v] && top[v] <= i && i <= bottom[v] {
                        adj[v].insert(u);
                    }
                }
            }
        }
        let mut indegree = vec![0; c];
        for u in 0..c {
            for &v in &adj[u] {
                indegree[v] += 1;
            }
        }
        let mut queue: VecDeque<usize> = VecDeque::new();
        let mut visited = 0;
        for u in 0..c {
            if indegree[u] == 0 {
                visited += 1;
                queue.push_back(u);
            }
        }
        while let Some(u) = queue.pop_front() {
            for &v in &adj[u] {
                indegree[v] -= 1;
                if indegree[v] == 0 {
                    visited += 1;
                    queue.push_back(v);
                }
            }
        }
        visited == c
    }
}

#[test]
fn test() {
    let target_grid = vec_vec_i32![[1, 1, 1, 1], [1, 2, 2, 1], [1, 2, 2, 1], [1, 1, 1, 1]];
    let res = true;
    assert_eq!(Solution::is_printable(target_grid), res);
    let target_grid = vec_vec_i32![[1, 1, 1, 1], [1, 1, 3, 3], [1, 1, 3, 4], [5, 5, 1, 4]];
    let res = true;
    assert_eq!(Solution::is_printable(target_grid), res);
    let target_grid = vec_vec_i32![[1, 2, 1], [2, 1, 2], [1, 2, 1]];
    let res = false;
    assert_eq!(Solution::is_printable(target_grid), res);
    let target_grid = vec_vec_i32![[1, 1, 1], [3, 1, 3]];
    let res = false;
    assert_eq!(Solution::is_printable(target_grid), res);
}

Having problems with this solution? Click here to submit an issue on github.