黒く塗られているマスの個数を \(m\) \((1\leq m\leq H\times W)\)とし、具体的に黒く塗られているマスがマス \((R_1,C_1)\), マス \((R_2,C_2)\), \(\ldots\), マス \((R_m,C_m)\) であるとします。
また、\(R_{\min}\), \(R_{\max}\), \(C_{\min}\), \(C_{\max}\) を、

\[ 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) \]

と定義します。

まず、問題について先に結論を述べると、「 \(R_{\min}\leq i\leq R_{\max}\) かつ \(C_{\min}\leq j\leq C_{\max}\) をみたす任意のマス \((i,j)\) がそれぞれ、黒く塗られている、または、まだ塗られていないのどちらかである（すなわち白く塗られていない）」\(\cdots(\bigstar)\) とき答えは Yes であり、そうでないとき No となります。

以下、このことを証明します。
まず、条件 \((\bigstar)\) がみたされるとき答えが Yes となることは比較的簡単に証明できます。 定義より、任意の黒いマス \((R_k,C_k)\) \((1\leq k\leq m)\) は \(R_{\min}\leq R_k\leq R_{\max}\) および \(C_{\min}\leq C_k\leq C_{\max}\) をみたすため、 「\(R_{\min}\leq i\leq R_{\max}\) かつ \(C_{\min}\leq j\leq C_{\max}\) 」 を みたさない マス \((i,j)\) は、白く塗られている、または、まだ塗られていない、のどちらかです。 よって、まだ塗られていないマスのうち「\(R_{\min}\leq i\leq R_{\max}\) かつ \(C_{\min}\leq j\leq C_{\max}\) 」をみたすものは黒く、そうでないものは白く塗ることで、黒マス全体が長方形をなすようにできます。
次に、条件 \((\bigstar)\) がみたされないときに答えが No となることを背理法で証明します。 条件 \((\bigstar)\) がみたされておらず、かつまだ塗られていないマスをうまく塗ることによって、「ある \(4\) つの整数の組 \((a,b,c,d)\) (\(1\leq a\leq b\leq H\), \(1\leq c\leq d\leq W\)) が存在して、\(a\leq i\leq b\) かつ \(c\leq j\leq d\) をみたすマス \((i,j)\) のみがすべて黒く、その他のマスが白く塗られている」状態にできたとします。 このとき、すでに黒く塗られているマス \((R_k,C_k)\) \((1\leq k\leq m)\) は \(a\leq R_k\leq b\) かつ \(c\leq C_k\leq d\) をみたしている必要があるため、 特に \(a\leq R_{\min}\)、\(R_{\max}\leq b\)、\(c\leq C_{\min}\)、\(C_{\max}\leq d\) が \(4\) つすべて成り立つことがわかります。 しかし、条件 \((\bigstar)\) がみたされないことから、ある白く塗られたマス \((i_0,j_0)\) が存在して \(R_{\min}\leq i_0\leq R_{\max}\), \(C_{\min}\leq j_0\leq C_{\max}\) をみたします。 このとき、\(a\leq R_{\min}\leq i_0\leq R_{\max}\leq b\), \(c\leq C_{\min}\leq j_0\leq C_{\max}\leq d\) となるため、 \(a\leq i\leq b\) かつ \(c\leq j\leq d\) をみたすマス \((i,j)\) がすべて黒く塗られている状態にすることができることと矛盾します。 よって、条件 \((\bigstar)\) がみたされていないならば答えが No になることがわかります。

次に、実際に判定する方法について、\(R_{\min}\), \(R_{\max}\), \(C_{\min}\), \(C_{\max}\) は全てのマスの状態を確認することで求めることができます。 その上で、\(R_{\min}\leq i\leq R_{\max}\) かつ \(C_{\min}\leq j\leq C_{\max}\) をみたすマス \((i,j)\) の状態を再度すべて確認することで、 条件 \((\bigstar)\) の判定を行うことができます。 計算量は \(O(HW)\) であり、十分高速です。
よってこの問題を解くことができました。

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;
}