Untitled

#include<iostream>
int n, m, A[100][100];
using namespace std;
bool ok;
int visited[100][100];

class Stack{
public:
    void init();
    int hang[100];
    int cot[100];
    int tophang;
    int topcot;
    int pophang();
    int popcot();
    int peekhang();
    int peekcot();
    void push(int i, int j);
    bool empty();
    
};
void Stack::init(){
    tophang=0;
    topcot=0;
}
bool Stack::empty(){
    if(tophang==-1 || topcot==-1) return true;
    return false;
}
int Stack::pophang(){
    int h = hang[tophang];
    tophang--;
    return h;
}
int Stack::popcot(){
    int c = cot[topcot];
    topcot--;
    return c;
}
int Stack::peekhang(){
    return hang[tophang];
    
}
int Stack::peekcot(){
    return cot[topcot];
}
void Stack::push(int i, int j){
    tophang++;
    topcot++;
    hang[tophang] = i;
    cot[topcot] = j;
}
Stack st;
int dem;
void check(){
	while(st.empty()==false){
		int i = st.pophang(), j = st.popcot();
		if(visited[i][j]==false){
			if(A[i+1][j]==1 && visited[i+1][j]==false){
				st.push(i+1, j);
				dem++;
			}
			else if(A[i][j+1]==1 && visited[i][j+1]==false){
				st.push(i, j+1);
				dem++;
			}
			else if(A[i-1][j]==1 && visited[i-1][j]==false){
				st.push(i-1, j);
				dem++;
			}
			else if(A[i][j-1]==1 && visited[i][j-1]==false){
				st.push(i, j-1);
				dem++;
			}
			else if(A[i-1][j]==2||A[i+1][j]==2||A[i][j-1]==2||A[i][j+1]==2){
				
				ok = true;
				
			}
			visited[i][j]=true;
			
		}
	}
}
int main(){
	int t;
	cin>>t;
	for(int tc=1; tc<=t; tc++){
		cin>>n>>m;
		st.init();
		int k = m, e=n;
		char x;
		if(n<m) n = m;
		for(int i=0; i<=n+1; i++){
			for(int j=0; j<=n+1; j++){
				A[i][j]=0;
				visited[i][j]=false;
			}
		}
		for(int i=0; i<=e+1; i++){
			for(int j=0; j<=k+1; j++){
				A[i][j] = 2;
			}
		}
		for(int i=1; i<=e; i++){
			for(int j=1; j<=k; j++){
				cin>>x;
				if(x=='#') A[i][j] = 0;
				else A[i][j] = 1;
			}
		}
		ok = false;
		dem=0;
		int count=0;
		for(int i=1; i<=e; i++){
			for(int j=1; j<=k; j++){
				if(i==1||i==e||j==1||j==k){

					if(A[i][j]==1) {
						count++;
						st.push(i, j);
						 if(count<2)check();
						
					}
				}
			}
		}

		if(dem==0) ok=false;
		if(count>2) ok = false;
		if(ok==false){
			cout<<"invalid"<<endl;
		}else cout<<"valid"<<endl;
		
	}
	return 0;
}
-------------------------------------------------------------------------------------------------
Input

6

4 4

####

#...

#.##

#.##

5 5

#.###

#..##

##..#

#.#.#

###.#

1 1

.

5 1

#

#

.

.

#

2 2

#.

.#

3 4

#..#

#.##

#.##

 

Output

valid

valid

invalid

valid

invalid

invalid