Simple Graph BFS


#1
int Solution::black(vector<string> &A)
{
	int n = A.size();
	int m = A[0].length();
	vector<vector < int>> Graph(n);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			int x = (A[i][j] == 'X') ? 1 : 0;
			Graph[i].push_back(x);
		}
	}

	bool visited[n][m];
	int ans = 0;
	memset(visited, false, sizeof(visited));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			queue<pair<int, int>> Q;
			if (Graph[i][j] == 1 && !visited[i][j])
			{
				ans++;
				Q.push(make_pair(i, j));
				visited[i][j] = true;
				while (!Q.empty())
				{
					pair<int, int> crr = Q.front();
					Q.pop();
					int x = crr.first;
					int y = crr.second;
					vector<pair<int, int>> conn_comp;
					if (x - 1 >= 0 && Graph[x - 1][y] == 1) conn_comp.push_back(make_pair(x - 1, y));
					if (y - 1 >= 0 && Graph[x][y - 1] == 1) conn_comp.push_back(make_pair(x, y - 1));
					if (x + 1 < n && Graph[x + 1][y] == 1) conn_comp.push_back(make_pair(x + 1, y));
					if (y + 1 < m && Graph[x][y + 1] == 1) conn_comp.push_back(make_pair(x, y + 1));
					for (auto u: conn_comp)
					{
						int x1 = u.first;
						int y1 = u.second;
						if (visited[x1][y1])
						{
							continue;
						}
						Q.push(make_pair(x1, y1));
						visited[x1][y1] = true;
					}
				}
			}
		}
	}
	return ans;
}