C - Paint to make a rectangle
Source: atcoder
Difficulty: 300

Problem Statement
You are given a grid of
H
rows and
W
columns.
Let
(i,j)
denote the cell at row
i
(
1 \leq i \leq H
) from the top and column
j
(
1 \leq j \leq W
) from the left.
The state of the grid is represented by
H
strings
S_1, S_2, \ldots, S_H
, each of length
W
, as follows:
If the
j
-th character of
S_i
is
#
, cell
(i,j)
is painted black.
If the
j
-th character of
S_i
is
.
, cell
(i,j)
is painted white.
If the
j
-th character of
S_i
is
?
, cell
(i,j)
is not yet painted.
Takahashi wants to paint each not-yet-painted cell white or black so that all the black cells form a rectangle.
More precisely, he wants there to exist a quadruple of integers
(a,b,c,d)
(
1 \leq a \leq b \leq H
,
1 \leq c \leq d \leq W
) such that:
For each cell
(i,j)
(
1 \leq i \leq H, 1 \leq j \leq W
),
if
a \leq i \leq b
and
c \leq j \leq d
, the cell is black;
otherwise, the cell is white.
Determine whether this is possible.
Constraints
1 \leq H, W \leq 1000
H
and
W
are integers.
Each
S_i
is a string of length
W
consisting of
#
,
.
,
?
.
There is at least one cell that is already painted black.
Input
The input is given from Standard Input in the following format:
H
W
S_1
S_2
\vdots
S_H
Output
If it is possible to paint all the not-yet-painted cells so that the black cells form a rectangle, print
Yes
; otherwise, print
No
.
Sample Input 1
3 5
.#?#.
.?#?.
?...?
Sample Output 1
Yes
The grid is in the following state.
?
indicates a cell that are not yet painted.
By painting cells
(1,3)
,
(2,2)
, and
(2,4)
black and cells
(3,1)
and
(3,5)
white, the black cells can form a rectangle as follows:
Therefore, print
Yes
.
Sample Input 2
3 3
?##
#.#
##?
Sample Output 2
No
To form a rectangle with all black cells, you would need to paint cell
(2,2)
black, but it is already painted white.
Therefore, it is impossible to make all black cells form a rectangle, so print
No
.
Sample Input 3
1 1
#
Sample Output 3
Yes

C++ solution:
#line 1 "C_Paint_to_make_a_rectangle.cpp"
#include <bits/stdc++.h>

template <class A, class B>
std::ostream& operator<<(std::ostream& ost, const std::pair<A, B>& p) {
    ost << "(" << p.first << ", " << p.second << ")";
    return ost;
}

template <class T>
std::ostream& operator<<(std::ostream& ost, const std::vector<T>& v) {
    ost << "[";
    for (int i = 0; i < v.size(); i++) {
        if (i) ost << ", ";
        ost << v[i];
    }
    ost << "]";
    return ost;
}

template <class T>
std::ostream& operator<<(std::ostream& ost, const std::set<T>& s) {
    ost << "{";
    bool first = true;
    for (const auto& v : s) {
        if (!first) ost << ", ";
        ost << v;
        first = false;
    }
    ost << "}";
    return ost;
}

template <class T, class U>
std::ostream& operator<<(std::ostream& ost, const std::map<T, U>& m) {
    ost << "{";
    bool first = true;
    for (const auto& [k, v] : m) {
        if (!first) ost << ", ";
        ost << k << ":" << v;
        first = false;
    }
    ost << "}";
    return ost;
}

void print() {}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    std::cout << head;
    if (sizeof...(Tail)) {
        std::cout << " ";
    }
    print(std::forward<Tail>(tail)...);
}

template <class... Args>
void println(Args&&... args) {
    print(args..., '\n');
}

#define SHOW(...)                                             \
    SHOW_IMPL(__VA_ARGS__, SHOW6, SHOW5, SHOW4, SHOW3, SHOW2, \
              SHOW1)(__VA_ARGS__)
#define SHOW_IMPL(_1, _2, _3, _4, _5, _6, NAME, ...) NAME
#define SHOW1(x) println(#x, "=", (x))
#define SHOW2(x, y) println(#x, "=", (x), #y, "=", (y))
#define SHOW3(x, y, z) println(#x, "=", (x), #y, "=", (y), #z, "=", (z))
#define SHOW4(x, y, z, w) \
    println(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w))
#define SHOW5(x, y, z, w, v)                                                 \
    println(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w), #v, "=", \
            (v))
#define SHOW6(x, y, z, w, v, u)                                              \
    println(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w), #v, "=", \
            (v), #u, "=", (u))

int Yes() {
    println("Yes");
    return 0;
}
int No() {
    println("No");
    return 0;
}

#define FOR1(a) for (int64_t _ = 0; _ < int64_t(a); ++_)
#define FOR2(i, a) for (int64_t i = 0; i < int64_t(a); ++i)
#define FOR3(i, a, b) for (int64_t i = a; i < int64_t(b); ++i)
#define FOR4(i, a, b, c) for (int64_t i = a; i < int64_t(b); i += (c))
#define FOR1_R(a) for (int64_t i = (a) - 1; i >= int64_t(0); --i)
#define FOR2_R(i, a) for (int64_t i = (a) - 1; i >= int64_t(0); --i)
#define FOR3_R(i, a, b) for (int64_t i = (b) - 1; i >= int64_t(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define rep(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define rep_r(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)

template <typename A, typename B>
inline void chmin(A& a, const B b) {
    if (a > b) a = b;
}
template <typename A, typename B>
inline void chmax(A& a, const B b) {
    if (a < b) a = b;
}

inline int32_t popcount(int64_t x) {
    return popcount(static_cast<uint64_t>(x));
}

#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define fi first
#define se second

#define int long long  // <= 64bit ミ(°_°)ミ

using vint = std::vector<int>;
using pint = std::pair<int, int>;
using vpint = std::vector<pint>;
using namespace std;

constexpr int INF = 1ll << 61;

signed main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // torichan

    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    rep(i, H) cin >> S[i];
    int min_y = INF, max_y = -INF, min_x = INF, max_x = -INF;
    rep(i, H) rep(j, W) if (S[i][j] == '#') {
        chmin(min_y, i);
        chmax(max_y, i);
        chmin(min_x, j);
        chmax(max_x, j);
    }
    rep(i, min_y, max_y + 1)
        rep(j, min_x, max_x + 1) if (S[i][j] == '.') return No();
    return Yes();
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	// H W
	// S1
	// S2
	// ...
	// SH
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	hwStr := strings.Split(sc.Text(), " ")
	h, err := strconv.Atoi(hwStr[0])
	if err != nil {
		panic(err)
	}
	w, err := strconv.Atoi(hwStr[1])
	if err != nil {
		panic(err)
	}
	s := make([]string, 0, h)
	for i := 0; i < h; i++ {
		sc.Scan()
		s = append(s, sc.Text())
	}

	var ti int
	breaked := false
	for i := 0; i < h; i++ {
		for j := 0; j < w; j++ {
			if s[i][j] == '#' {
				ti = i
				breaked = true
				break
			}
		}
		// goto使った方がいいんだろうね
		if breaked {
			break
		}
	}

	var bi int
	breaked = false
	for i := h - 1; i >= 0; i-- {
		for j := 0; j < w; j++ {
			if s[i][j] == '#' {
				bi = i
				breaked = true
				break
			}
		}
		if breaked {
			break
		}
	}

	var lj int
	breaked = false
	for j := 0; j < w; j++ {
		for i := 0; i < h; i++ {
			if s[i][j] == '#' {
				lj = j
				breaked = true
				break
			}
		}
		if breaked {
			break
		}
	}

	var rj int
	breaked = false
	for j := w - 1; j >= 0; j-- {
		for i := 0; i < h; i++ {
			if s[i][j] == '#' {
				rj = j
				breaked = true
				break
			}
		}
		if breaked {
			break
		}
	}

	ok := true
	breaked = false
	for i := ti; i <= bi; i++ {
		for j := lj; j <= rj; j++ {
			if s[i][j] == '.' {
				ok = false
				breaked = true
				break
			}
		}
		if breaked {
			break
		}
	}

	if ok {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}

Java solution:
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();

        // take the furthest left black cell, furthest right black cell, furthest top, furthest bottom, and see if all of them are black or unpainted
        // otherwise no?
        // black is #, white is ., unpainted is ?
        int h = sc.nextInt(), w = sc.nextInt();
        char[][] arr = new char[h][w];

        for (int i=0;i<h;i++) {
            char[] s = sc.nextLine().toCharArray();

            for (int j=0;j<w;j++) {
                arr[i][j] = s[j];
            }
        }

        // fLeft = 1, fRight = 3, fTop = 0, fBottom = 1
        // 

        // iterate through entire thing, check for furthest left cell aka lowest w
        int fLeft = Integer.MAX_VALUE, fRight = Integer.MIN_VALUE, fTop = Integer.MAX_VALUE, fBottom = Integer.MIN_VALUE;

        for (int i=0;i<h;i++) {
            for (int j=0;j<w;j++) {
                if (arr[i][j] == '#') {
                    fLeft = Math.min(j, fLeft);
                    fRight = Math.max(j, fRight);

                    fTop = Math.min(i, fTop);
                    fBottom = Math.max(i, fBottom);
                }
            }
        }

        // System.out.println("fLeft: " + fLeft);
        // System.out.println("fRight: " + fRight);
        // System.out.println("fTop: " + fTop);
        // System.out.println("fBottom: " + fBottom);

        for (int i=fLeft;i<fRight+1;i++) {
            for (int j=fTop;j<fBottom+1;j++) {
                // System.out.println(i + ", " + j);
                if (arr[j][i] == '.') {
                    System.out.println("No");
                    return;
                }
            }
        }

        System.out.println("Yes");
    }

    public static class FastScanner {

        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

JavaScript solution:
function Main(input) {
    inputArray = input.split("\n");
    const [H,W] = inputArray[0].split(" ").map(Number);
    let xMinB = W-1;
    let xMaxB = 0;
    let yMinB = H-1;
    let yMaxB = 0;
    let msg = 'Yes'
    // console.log(H,W)
    for(let i=0;i<H;i++){
        for(let j=0;j<W;j++){
            if(inputArray[i+1][j]=='#'){
                // console.log(i+1,j+1)
                if(xMinB > j){
                    xMinB = j 
                }
                if(xMaxB < j){
                    xMaxB = j
                }
                if(yMinB > i){
                    yMinB = i
                }
                if(yMaxB < i){
                    yMaxB = i
                }   
            } 
            // console.log(inputArray[i+1][j])
        }
    }

    // console.log(xMinB,xMaxB,yMinB,yMaxB)

    for(let i=yMinB;i<=yMaxB;i++){
        for(let j=xMinB;j<=xMaxB;j++){
            if(inputArray[i+1][j]=='.'){
                msg = 'No'
            } 
            // console.log(inputArray[i+1][j])
        }
    }
    console.log(msg)

}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Python solution:
H, W = [int(i) for i in input().split()]
S = []
u, d = -1, -1
l, r = H, -1
for i in range(H):
  s = input()
  if u == -1 and "#" in s:
    u = i
  if "#" in s:
    d = i
    r = max(r, s.rfind("#"))
    l = min(l, s.find("#"))
  S.append(s)
for i in range(u, d + 1):
  if "." in S[i][l : r + 1]:
    exit(print("No"))
print("Yes")

Ruby solution:
H, W = gets.split.map( &:to_i )

@l_b = [ -1, W ]
@r_b = [ -1, W ]
@line = ""

#
#        . ? ?  ?    #  - - (#|?) - -  #     .
#        ^           ^                 ^     ^
#    l_b[0]         l_b[1]         r_b[0]    r_b[1]
#
def state_1( l )
  w = @line.rindex( '.', l ) || -1
  # [ lw, l ]               #  .  _ _   #
  #                            w       l
  @l_b[0] = [@l_b[0], w ].max
  @l_b[1] = [@l_b[1], l ].min
  
  r = @line.rindex( '#' )
  w = @line.index( '.', r ) || W
  # [ r, rw ]               #  #  _ _ _ .
  #                            r        w
  @r_b[0] = [@r_b[0], r ].max
  @r_b[1] = [@r_b[1], w ].min

  w = @line.index( '.', l ) || W
#  p [@l_b, @r_b, w]
  return false if @l_b[0] >= @l_b[1]
  return false if @r_b[0] >= @r_b[1]

  return false if w < @r_b[0]
  true
end

def state_2
  @l_b[0] = @line.rindex( '.', @l_b[1] ) || @l_b[0]
  @r_b[1] = @line.index(  '.', @r_b[0] ) || @r_b[1]
end

def main

  @state = 0

  H.times {|i|
    @line = gets
    l = @line.index( '#' )         #   * * * # * # * # * * *
    #         l
    case @state
    when 0
      next if l.nil?
      @state = 1
      return  false unless state_1( l )
    when 1
      if l.nil?                #  ? ? ? ? .  ? . ? ? ? 
        state = 2
        return false unless state_2
        next
      end
      return false unless state_1( l )
    when 2
      if l.nil?
        return false unless state_2
        next
      end
      @state = 1
      return false unless state_1
    end
  }
  true
end

puts  main ? "Yes" : "No"