bfs.cpp

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

	int solution (vector<vector<char> > &A, int K) {
	   // Write your code here
	   long int i,j;
	   long int fans = 0;
	  // cout<<"ss"<<A.size()<<A[0].size()<<" "<<A[1].size()<<" "<<A[2].size()<<endl;
	   for(i=0;i<A.size();i++){
	       queue<pair<long int,long int > > q;
	       vector<bool> visited(A[i].size(),false);
	       for(j=0;j<A[i].size();j++){
	           //cout<<"A[i][j]"<<A[i][j]<<"i and j "<<i<<"  "<<j<<" "<<visited[j]<<endl;
	           if(A[i][j] == 'T' && visited[j] == 0){
	           	//	cout<<"ON:"<<i<<" "<<j<<endl;
	               pair<long int,long int>P(0,j);
	               q.push(P);
	               visited[j] = 1;
	               int diff[][2] = {{0,1},{0,-1}};
	               //bool flag = 0;
	               while(!q.empty()){
	                   pair<long int,long int> curr = q.front();
	                   q.pop();
	                  // cout<<"curr and i "<<curr.second<<" "<<i<<endl;
	                   visited[curr.second] = 1;
	                    bool flag = 0;
	                    for(long int t=curr.second+1;(t-curr.second <= K) &&(t<A[i].size());t++){
	                        if(A[i][t] == 'T' && visited[t] == 0){
	                            pair<long int,long int > pp(0,t);
	                     //       cout<<"pushing:"<<i<<" "<<t<<endl;
	                            q.push(pp);
	                            visited[t] = 1;
	                        }
	                        else if(A[i][t] == 'P' && flag == 0){
	                            //cout<<"pair ->"<<t<<" "<<curr.second<<" "<<i<<endl;
	                            fans++;
	                            A[i][t] = 'E';
	                            flag = 1;
	                       //     cout<<"pair ->"<<t<<" "<<curr.second<<" "<<i<<" "<<flag<<endl;
	                        }
	                    }
	                    //if(flag == 0)
	  //              	cout<<flag<<"bert"<<endl;
	                for(long int t=curr.second-1;(curr.second-t <= K)&& t>=0;t--){
	                        if(A[i][t] == 'T' && visited[t] == 0){
	                            pair<long int,long int > pp(0,t);
	                            q.push(pp);
	                            visited[t] = 1;
	                        }
	                        else if(A[i][t] == 'P' && flag == 0){
	//                            cout<<"pair ->"<<t<<" "<<curr.second<<" "<<i<<" "<<flag<<endl;
	                            fans++;
	                            flag = 1;
	                            A[i][t] = 'E';
	                        }
	                	}
	               }
	               //break;
	           }
	       }
	   }
	   return fans;
	}

	int main() {

	    ios::sync_with_stdio(0);
	    cin.tie(0);
	    int T;
	    cin >> T;
	    for(int t_i=0; t_i<T; t_i++)
	    {
	        int N;
	        cin >> N;
	        int K;
	        cin >> K;
	        vector<vector<char> > A(N, vector<char>(N));
	        for (int i_A=0; i_A<N; i_A++)
	        {
	        	for(int j_A=0; j_A<N; j_A++)
	        	{
	        		cin >> A[i_A][j_A];
	        	}
	        }

	        int out_;
	        out_ = solution(A, K);
	        cout << out_;
	        cout << "\n";
	    }
	}