SW expert-파핑파핑 지뢰찾기.cpp.txt

#include<iostream>
#include<vector>
#include<fstream>
#include<string>
#include<queue>

using namespace std;
char arr[301][301];
bool visit[301][301];
int dx[8] = { -1,1,0,0,-1,-1,1,1 };
int dy[8] = { 0,0,-1,1,-1,1,-1,1 };
int N;

void simulate(int x, int y)
{
	int ret = 0;

	for (int i = 0; i < 8; i++)
	{
		int Gx = x + dx[i];
		int Gy = y + dy[i];
		if (Gx >= 0 && Gx < N&&Gy >= 0 && Gy < N)
		{
			if (arr[Gx][Gy] == '*')
				ret++;
		}
	}
	arr[x][y] = ret+'0';
}

int main()
{
	int testcase,countT;
	cin >> testcase;
	countT = 1;
	while (testcase!=0)
	{
		cin >> N;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
				cin >> arr[i][j];
		}

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				visit[i][j] = false;
				if (arr[i][j] != '*')
				{
					simulate(i, j);
				}
			}
		}

		queue<pair<int, int>> q;
		int ret = 0;

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (arr[i][j] == '0' && !visit[i][j])
				{
					ret++;
					q.push(make_pair(i, j));
					visit[i][j] = true;

					while (!q.empty())
					{
						int x = q.front().first;
						int y = q.front().second;
						q.pop();

						bool check_insert = true;

						for (int k = 0; k < 8; k++)
						{
							int Gx = x + dx[k];
							int Gy = y + dy[k];
							if (Gx >= 0 && Gx < N&&Gy >= 0 && Gy < N)
							{
								if (arr[Gx][Gy] == '*')
									check_insert = false;
							}
						}

						if (check_insert)
						{
							for (int k = 0; k < 8; k++)
							{
								int Gx = x + dx[k];
								int Gy = y + dy[k];
								if (Gx >= 0 && Gx < N&&Gy >= 0 && Gy < N && !visit[Gx][Gy])
								{
									visit[Gx][Gy] = true;
									q.push(make_pair(Gx, Gy));
								}
							}
						}

					}
				}

			}
		}

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (arr[i][j] != '*' && !visit[i][j])
					ret++;
			}
		}



		cout << "#" <<countT++<<" "<<ret<< endl;
		testcase--;
	}
	
	return 0;
}