Untitled

Validate the maze
There are many algorithms to generate maze. After generating the maze we’ve to validate whether it’s a valid maze or not. A valid maze has exactly one entry point and exactly one exit point (exactly 2 openings in the edges) and there must be atleast one path from the entry point to exit point.
 
Given a maze, just find whether the maze is "valid" or "invalid".

Input
The first line consists of an integer t, the number of test cases. Then for each test case, the first line consists of two integers m and n, the number of rows and columns in the maze. Then contains the description of the matrix M of order mxn. M[i][j] = # represents a wall and M[i][j] = '.' represents a space.
Output
 For each test case find whether the maze is "valid" or "invalid".
 
Constraints

1 <= t< = 10000
1 <= m< = 20
1 <= n< = 20

Sample
 
Input
6
4 4
####
#...
#.##
#.##
5 5
#.###
#..##
##..#
#.#.#
###.#
1 1
.
5 1
#
#
.
.
#
2 2
#.
.#
3 4
#..#
#.##
#.##
 
Output
valid
valid
invalid
valid
invalid
invalid


#include <conio.h>
#include <iostream>
#define MAX 21

using namespace std;
int T, testcase, N,M, startX, startY, endX, endY;
int Answer;
char data[MAX][MAX];
int doors[MAX][MAX];
int visited[MAX][MAX];
int dx[4] = {-1,0,0,1};
int dy[4] = {0,-1,1,0};
struct point{
	int x;
	int y;
};

point Queue[1000000];

int front, rear;

void resetQueue(){
	front=rear=0;
}

bool isEmpty(){
	return front>=rear;
}

void push(int x, int y){
	Queue[rear].x = x;
	Queue[rear].y = y;
	rear++;
}

point pop(){
	point a = Queue[front];
	front++;
	return a;
}

bool check_door(){
	int door_num=0;
	int hang[2] = {0, N-1};
	for (int i = 0; i < M; i++)
	{
		for (int hang_idx = 0; hang_idx < 2; hang_idx++)
		{
			if (data[hang[hang_idx]][i]=='.' && doors[hang[hang_idx]][i]==0)
			{
				door_num++;
				doors[hang[hang_idx]][i]=1;
				if (door_num==1)
				{
					startX=hang[hang_idx];
					startY =i;
				}
				if (door_num==2)
				{
					endX=hang[hang_idx];
					endY =i;
				}
			}
		}
		
	}

	int cot[2] = {0, M-1};
	for (int i = 0; i < N; i++)
	{
		for (int cot_idx = 0; cot_idx < 2; cot_idx++)
		{
			if (data[i][cot[cot_idx]]=='.' && doors[i][cot[cot_idx]]==0)
			{
				doors[i][cot[cot_idx]]=1;
				door_num++;
				if (door_num==1)
				{
					startX=i;
					startY =cot[cot_idx];
				}
				if (door_num==2)
				{
					endX=i;
					endY =cot[cot_idx];
				}
			}
		}
		
	}
	return door_num==2;
}

void BFS(){
	resetQueue();
	visited[startX][startY]=1;
	push(startX,startY);
	while (!isEmpty())
	{
		point temp = pop();
		int cur_x = temp.x;
		int cur_y = temp.y;
		int nx, ny;
		for (int i = 0; i < 4; i++)
		{
			nx = cur_x+dx[i];
			ny = cur_y+dy[i];

			if (nx>-1 && nx<N && ny>-1 && ny<M)
			{
				if (data[nx][ny]=='.' && visited[nx][ny]==0)
				{
					if (nx==endX && ny==endY)
					{
						Answer=1;
						return;
					}
					else{
						visited[nx][ny]=1;
						push(nx, ny);
					}
				}
			}
		}
	}
}

int main(){

	freopen("Text.txt","r",stdin);

	cin>>T;
	for (testcase = 1; testcase<=T; testcase++)
	{
		Answer = 0;
		startX =-1;
		startY =-1;
		endX =-1;
		endY =-1;
		cin>>N>>M;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				cin>>data[i][j];
				doors[i][j]=0;
				visited[i][j]=0;
			}
		}

		
		if (check_door())
		{
			BFS();
			if (Answer==1)
			{
				cout<<"valid"<<endl;
			}
			else{
				cout<<"invalid"<<endl;
			}
		}
		else{
			cout<<"invalid"<<endl;
		}
		
	}

	getch();
	return 0;
}

20
4 4
####
#...
#.##
#.##
5 5
#.###
#..##
##..#
#.#.#
###.#
1 1
.
5 1
#
#
.
.
#
2 2
#.
.#
3 4
#..#
#.##
#.##
10 10
##########
.....#.#.#
#.##.##..#
##.#...#.#
#..#...#.#
#......###
######.###
######.###
######..##
#######.##
6 5
##.##
#..##
#...#
###.#
#...#
###.#
9 9
#########
..#.#####
#.#.#.#.#
#....##.#
###...###
#..##...#
#.#...#..
#.#..#..#
#########
6 8
...#.###
####..#.
.#####.#
.#..##.#
##.####.
..###.##
8 6
..##..
###...
#....#
.#.##.
.##.#.
.#.##.
.#..#.
##....
14 8
##.#####
#......#
##.##.##
###...##
##...#..
#..#.#.#
###....#
###.####
#####.##
###..#.#
######.#
#.#..###
#....###
########
19 10
...###.#..
.#.###.###
..........
.#.#####.#
#.#.#.#.#.
..##.####.
#.##.#..##
##..#.#...
#..#.#..#.
.##.###..#
......#.##
#####..#..
#####.#.#.
.##.###.##
##...###.#
#....##..#
##...#....
#.#.##..##
.#..#.##..
15 10
.#.##....#
....#....#
#.##.##.#.
#.....###.
.#.###.###
...#.##.#.
.###..#.##
##..#.#..#
#####..#..
#..#.##.##
..#....#.#
...#....##
####.#.###
...##..###
.#..####.#
11 6
######
..####
#.#..#
#..#.#
##...#
####.#
#....#
#.##.#
#...##
#.#.##
#.####
10 5
#..#.
#.#..
.###.
#.#.#
.###.
.###.
#....
.##.#
.#...
....#
13 20
######.#############
#......###..##...#.#
#.#.##.#....##..####
#.#..###.##...##.#.#
#..#.###..#.#....###
##...#...#.....##.##
##.##..#..#...#.#..#
##....###...###.##.#
#..###.#........##.#
###.#.....#...#..#.#
#...####.#####..####
#..#.#..##...##..#.#
################.###
7 9
#####.###
####...##
#....####
##.##.#.#
##.#...##
##....#.#
####.####
17 15
...#.#.....##..
#.##.#.##......
.##.#....#.####
.####.....##.#.
##..#.#..####..
#.....#.#.##..#
##..#.#..#####.
.###.#.#..#.#..
#..####...####.
###.###.##.#.#.
###.#..#.##.###
#.####...##.###
##.####..#.#.#.
#.##..#.###.#..
#.######.#.....
.###.#.#.#..#.#
..#.#.#.###....
14 9
#########
#######.#
#........
###..##.#
##....###
#####..##
#..###..#
##.....##
##.#.##.#
##.#.#..#
##.#.####
#..##...#
##...####
####.####


valid
valid
invalid
valid
invalid
invalid
valid
valid
valid
invalid
invalid
valid
invalid
invalid
valid
invalid
valid
valid
invalid
valid