Suppose that there are \(m\) cells painted black \((1\leq m\leq H\times W)\), specifically cell \((R_1,C_1)\), cell \((R_2,C_2)\), \(\ldots\), and cell \((R_m,C_m)\).
Also, define \(R_{\min}\), \(R_{\max}\), \(C_{\min}\), and \(C_{\max}\) as

\[ R_{\min}=\min_{1\leq k\leq m} (R_i),\quad R_{\max}=\max_{1\leq k\leq m} (R_i) \\ C_{\min}=\min_{1\leq k\leq m} (C_i),\quad C_{\max}=\max_{1\leq k\leq m} (C_i) . \]

We claim the conclusion first: the answer is Yes if every cell \((i,j)\) with \(R_{\min}\leq i\leq R_{\max}\) and \(C_{\min}\leq j\leq C_{\max}\) is either painted black or not painted yet (i.e. is not pained white) \(\cdots(\bigstar)\), and No otherwise.

We will prove that claim.
First, we can relatively easily show that if the condition \((\bigstar)\) is satisfied, then the answer is Yes. By definition, every black cell \((R_k,C_k)\) \((1\leq k\leq m)\) satisfies \(R_{\min}\leq R_k\leq R_{\max}\) and \(C_{\min}\leq C_k\leq C_{\max}\), so every cell \((i,j)\) that does not satisfy “\(R_{\min}\leq i\leq R_{\max}\) and \(C_{\min}\leq j\leq C_{\max}\)” is either painted white or unpainted yet. Thus, among the unpainted cells, we can paint those with \(R_{\min}\leq i\leq R_{\max}\) and \(C_{\min}\leq j\leq C_{\max}\) and black, and the others white, so that the black square forms a rectangle.
Next, we will show that if the condition \((\bigstar)\) is not satisfied, then the answer is No, by contradiction. Suppose that the condition \((\bigstar)\) is violated, while we could paint the unpainted cells so that there exists a quadruple \((a,b,c,d)\) of integers (\(1\leq a\leq b\leq H\), \(1\leq c\leq d\leq W\)) such that cells \((i,j)\) with \(a\leq i\leq b\) and \(c\leq j\leq d\) are painted black and the others white. Then, an initially-black cell \((R_k,C_k)\) \((1\leq k\leq m)\) must satisfy \(a\leq R_k\leq b\) and \(c\leq C_k\leq d\), so especially we have \(a\leq R_{\min}\), \(R_{\max}\leq b\), \(c\leq C_{\min}\), and \(C_{\max}\leq d\). However, sine the condition \((\bigstar)\) is violated, there exists a white cell \((i_0,j_0)\) such that \(R_{\min}\leq i_0\leq R_{\max}\) and \(C_{\min}\leq j_0\leq C_{\max}\). In this case, we have \(a\leq R_{\min}\leq i_0\leq R_{\max}\leq b\) and \(c\leq C_{\min}\leq j_0\leq C_{\max}\leq d\), so it contradicts with the assumption that we can make all the cells \((i,j)\) with \(a\leq i\leq b\) and \(c\leq j\leq d\) black. Therefore, we have proved that if the condition \((\bigstar)\) holds, then the answer is No.

We will describe how to actually check the condition. We can find \(R_{\min}\), \(R_{\max}\), \(C_{\min}\), and \(C_{\max}\) by actually inspecting all the cells. Then we can check the status of all the cell \((i,j)\) with \(R_{\min}\leq i\leq R_{\max}\) and \(C_{\min}\leq j\leq C_{\max}\) again to check the condition \((\bigstar)\). The time complexity is \(O(HW)\), which is fast enough.
Therefore, the problem has been solved.

Sample code in C++:

#include <bits/stdc++.h>
using namespace std;

int main(void){
	int h,w;
	string s[1000];
	int hmin=1000,hmax=-1,wmin=1000,wmax=-1;
	bool flag=true;

	cin>>h>>w;

	for(int i=0;i<h;i++){
		cin>>s[i];
		for(int j=0;j<w;j++){
			if(s[i][j]=='#'){
				hmin=min(hmin,i);
				hmax=max(hmax,i);
				wmin=min(wmin,j);
				wmax=max(wmax,j);
			}
		}
	}

	for(int i=hmin;i<=hmax;i++){
		for(int j=wmin;j<=wmax;j++){
			if(s[i][j]=='.')flag=false;
		}
	}

	if(flag)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}