Skip to content

Instantly share code, notes, and snippets.

@Sharma96 Sharma96/bfs.cpp Secret
Created Sep 22, 2017

Embed
What would you like to do?
#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";
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.