please can any one help me to know why I am getting WA the problem is a very simple bfs and I am really sure of the code
include
using namespace std;
typedef long long ll;
int n , m , t ;
int dx[]={0 , 0 , 1 , -1};
int dy[]={1 ,-1 , 0 , 0};
bool visited[20][20] ;
char M[20][20] ;
vector <pair > enter ;
queue <pair > q ;
pair p;
void clear_all ()
{
enter.clear() ;
while(!q.empty())q.pop();
for (int i = 0 ; i < 20 ; i++){
for (int j = 0 ; j < 20 ;j++)visited[i][j] = false ;
}
}
bool Valid (){
int open = 0 ;
for (int i = 0 ; i < n ; i++){
if (M[i][0] == '.'){open++ ;enter.push_back(make_pair(i , 0)) ;}
if (M[i][m-1] == '.' && m - 1 != 0){open++ ;enter.push_back(make_pair(i , m-1)) ;}
}
for (int i = 1 ; i < m - 1 ;i++ ){
if (M[0][i] == '.'){open++ ;enter.push_back(make_pair(0, i)) ;}
if (M[n-1][i] == '.' && n - 1 != 0 ){open++ ;enter.push_back(make_pair(n-1 , i)) ;}
}
//cout << open << endl;
if (open != 2 )return false ;
else return true ;
}
int main()
{
cin >> t ;
while (t -- ){
cin >> n >> m ;
bool done = false ;
for (int i = 0 ; i < n ; i ++){
for (int j = 0 ; j < m ; j ++){ cin >> M[i][j] ;}
}
if ( ! Valid() ){cout << "invalid" << endl; clear_all() ;continue ;}
p.first = enter[0].first , p.second = enter[0].second ;
q.push(p) ;
while (!q.empty() && !done){
p = q.front() ;
visited[p.first][p.second] =true ;
q.pop();
for (int i = 0 ; i < 4 ; i++){
int newx = p.first + dx[i] ;
int newy = p.second + dy[i] ;
// cout <<"b newx = "<<newx <<" b newy = "<< newy<< endl;
if (newx > n || newy > m || newx < 0 || newy < 0 )continue ;
else {
if (M[newx][newy] == '.'){
// cout <<"newx = "<<newx <<" newy = "<< newy<< endl;
if (newx == enter[1].first && newy == enter[1].second)
{done = true ; cout <<"valid"<<endl; break ;}
else if (!visited[newx][newy])
{q.push( {newx , newy} ) ;}
}
}
}
}
if (!done)cout <<"invalid"<< endl;
clear_all() ;
}
}