India is well known for its spirituality and holy places, a holy place is represented by '*' (rest of the cities are represented by '.'), and all the cities which are neighbors (which shares a corner or a side) to holy places are known as spiritual cities. Geek wants to travel all spiritual places, but he decided to travel from one city to another city if both of them are spiritual and neighbors too. The task is to find the maximum number of spiritual cities geek can travel, starting from a spiritual city. Note: A holy place is not considered as a spiritual city Input: 1. The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases is as follows. 2. The first line of each test case contains two space-separated integers N and M. 3. Next N lines contain M characters Output: For each test case, print the maximum number of spiritual cities geek can travel. Your Task: This is a function problem. You only need to complete the function maxCities() that take a 2-d vector of char, m, n as parameters and returns the maximum number of spiritual cities geek can travel. The driver code automatically appends a new line. Constraints: 1. 1 <= T <= 100 2. 1 <= N, M <= 102 Example: Input: 2 5 5 ....* ..... ..*.. ..... ..... 1 2 ** Output: 10 0 Explanation: Testcase 1: (1, 4), (2, 2), (2, 3), (2, 4), (2, 5), (3, 2), (3, 4), (4, 2), (4, 3), (4, 4) are the spiritual cities which geek will visit
Answers
Answer:
#include<bits/stdc++.h>
using namespace std;
int maxCities(vector<vector<char>> &a, int n, int m);
// Driver code to test above functions
int main()
{
int t;
cin >> t;
while(t--)
{
int n, m;
cin >> n >> m;
vector<vector<char>> a(n, vector<char>(m));
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
cin >> a[i][j];
}
}
cout << maxCities(a, n, m) << "\n";
}
return 0;
}// } Driver Code Ends
int maxCities(vector<vector<char>> &s, int n, int m)
{
// Your code goes here
int a[n][m];
memset(a, 0, sizeof(a));
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if(s[i][j] == '*')
{
if(i-1 >= 0 && j-1 >= 0 && s[i-1][j-1] == '.')
a[i-1][j-1] = 1;
if(i-1 >= 0 && j >= 0 && s[i-1][j] == '.')
a[i-1][j] = 1;
if(i-1 >= 0 && j+1 < m && s[i-1][j+1] == '.')
a[i-1][j+1] = 1;
if(i+1 < n && j-1 >= 0 && s[i+1][j-1] == '.')
a[i+1][j-1] = 1;
if(i+1 < n && j >= 0 && s[i+1][j] == '.')
a[i+1][j] = 1;
if(i+1 < n && j+1 < m && s[i+1][j+1] == '.')
a[i+1][j+1] = 1;
if(j-1 >= 0 && s[i][j-1] == '.')
a[i][j-1] = 1;
if(j+1 < m && s[i][j+1] == '.')
a[i][j+1] = 1;
}
}
}
int vis[n][m];
memset(vis, 0, sizeof(vis));
int ans = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if(vis[i][j])
continue;
queue<pair<int,int>> q;
q.push({i, j});
int res = 0;
while(!q.empty())
{
int x = q.front().first, y = q.front().second;
q.pop();
if(x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && a[x][y])
{
res++;
vis[x][y] = 1;
for(int xx = -1; xx <= 1; xx++)
{
for(int yy = -1; yy <= 1; yy++)
{
q.push({x+xx, y+yy});
}
}
}
}
ans = max(ans, res);
}
}
return ans;
}
Explanation:
Graph traversal, either do bfs or dfs.