전등 밝히기

source.cpp

#define TIMETEST 0

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#if (TIMETEST)
#include <chrono>//for time check
#endif

using namespace std;

struct Vec2{
	int x;
	int y;
	Vec2(int _x,int _y)
	{
		x=_x;
		y=_y;
	}
};

vector< vector<int> > _map;

int main()
{
#if (TIMETEST)
	std::chrono::duration<double> sec;
#endif
	std::ios::sync_with_stdio(false);
#if (TIMETEST)
	std::chrono::system_clock::time_point start = std::chrono::system_clock::now();
#endif
	int n = 0;
	cin>>n;//testcase <=100
	for(int i=0;i<n;i++)
	{
		
		string buf;
		int w,h,d;
		cin>>w>>h>>d;
		cin.ignore();
		_map.resize(h);
		for(int j=0;j<h;j++)
		{
			_map[j].resize(w);
			getline(cin,buf);
			for(int k=0;k<w;k++)
			{
				if(buf[k]=='#')
					_map[j][k]=-1;//-1 is wall
				else
					_map[j][k]=0;
			}
		}

		//check map
		/*
		for(int j=0;j<h;j++)
		{
			for(int k=0;k<w;k++)
				cout<<_map[j][k]<<" ";
			cout<<endl;
		}
		*/

		int maxVal=0;
		int maxPointCount=0;//maximum point count
		vector<Vec2> maxPoints;//maximum point array

		//for loop check 4-intersection, 3-intersection
		for(int j=1;j<h-1;j++)
		{
			for(int k=1;k<w-1;k++)
			{
				if(_map[j][k]!=-1)
				{
					if(_map[j-1][k]!=-1)
						_map[j][k]++;
					if(_map[j+1][k]!=-1)
						_map[j][k]++;
					if(_map[j][k-1]!=-1)
						_map[j][k]++;
					if(_map[j][k+1]!=-1)
						_map[j][k]++;
					if(maxVal==_map[j][k])
					{
						maxPoints.push_back(Vec2(j,k));
						maxPointCount++;
					}
					else if(maxVal<_map[j][k])
					{
						//reset and restore
						maxPoints.clear();
						maxPointCount=0;
						maxPoints.push_back(Vec2(j,k));
						maxPointCount++;

						maxVal=_map[j][k];
					}
				}
			}
		}
		int maxPointNum=0;
		int maxDistance=0;
		int resMaxArea=0;
		//for loop find longest way and ++
		for(int j=0;j<maxPointCount;j++)
		{
			bool left = false;
			bool right = false;
			bool up = false;
			bool down = false;

			maxDistance = 1;

			//go left, right, up, down -> count maxDistance
			for (int k=1;k<d;k++) 
			{
				if (maxPoints[j].x-k>=0 && up==false && _map[maxPoints[j].x-k][maxPoints[j].y]!=-1) 
						maxDistance++;
				else
					up=true;

				if (maxPoints[j].y-k>=0 && left==false && _map[maxPoints[j].x][maxPoints[j].y-k]!=-1) 
						maxDistance++;
				else
					left = true;

				if (maxPoints[j].x+k<h && down==false && _map[maxPoints[j].x+k][maxPoints[j].y]!=-1) 
						maxDistance++;
				else
					down = true;

				if (maxPoints[j].y+k<w && right==false && _map[maxPoints[j].x][maxPoints[j].y+k]!=-1)
						maxDistance++;
				else
					right = true;
			}

			if (resMaxArea<maxDistance) 
			{
				resMaxArea=maxDistance;
				maxPointNum=1;
			}
			else if (resMaxArea==maxDistance) 
				maxPointNum++;
		}
		cout<<maxPointNum<<" "<<resMaxArea<<endl;
		_map.clear();
	}
#if (TIMETEST)
	sec = std::chrono::system_clock::now() - start;
	cout<<"time : "<<sec.count()<<"secs"<<endl;
#endif
	return 0;
}