백준(BOJ) 17085번 십자가 2개 놓기 (수정)

문제 : https://www.acmicpc.net/problem/17085

17085번: 십자가 2개 놓기

풀이 :

기존에는 a를 모두 늘리고 b를 구했지만 재채점 이후로는 틀리다고 나오므로

 

a를 늘리는 도중에 b를 늘리면서 ans를 구하는 방식으로 접근했습니다.

 

전체 n*m이 작기에 충분히 시간 안에 가능합니다.

 

코드 ( C++ )

	#include <queue>
	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <cstring>
	using namespace std;
	int n, m;
	char a[16][16];
	const int dy[4] = { 1,-1,0,0 };
	const int dx[4] = { 0,0,1,-1 };
	vector<pair<int, int>> v;
	bool check[16][16] = { false, };
	int ans;
	void find(int fy, int fx, int ey,int ex)
	{
	int cnt;
	for (cnt = 0; ; ++cnt) {
	bool flg = true;
	for (int i = 0; i < 4; ++i) {
	int ny = fy + dy[i] * cnt;
	int nx = fx + dx[i] * cnt;
	if (!(0 <= ny && ny < n && 0 <= nx && nx < m)) {
	flg = false;
	break;
	}
	if (a[ny][nx] == '.') {
	flg = false;
	break;
	}
	}
	if (!flg) {
	break;
	}
	//통과했으니 check배열 입력
	for (int j = 0; j < 4; ++j) {
	int ny = fy + dy[j] * cnt;
	int nx = fx + dx[j] * cnt;
	check[ny][nx] = true;
	}
	//B 구하기
	int bcnt;
	int bflg = true;
	for (bcnt = 0; ; ++bcnt) {
	for (int i = 0; i < 4; ++i) {
	int ny = ey + dy[i] * bcnt;
	int nx = ex + dx[i] * bcnt;
	if (!(0 <= ny && ny < n && 0 <= nx && nx < m)) {
	bflg = false;
	break;
	}
	if (a[ny][nx] == '.') {
	bflg = false;
	break;
	}
	if (check[ny][nx] == true) {
	bflg = false;
	break;
	}
	}
	if (bflg) {
	//여기서 answer 구해야함
	int A = (cnt) * 4 + 1;
	int B = (bcnt) *4 + 1;
	ans = max(ans, A*B);
	}
	else
	break;
	}
	}
	}
	void solve(vector<pair<int, int>> p, int begin)
	{
	if (p.size() == 2) {
	memset(check, 0, sizeof(check));
	int fy = p[0].first;
	int fx = p[0].second;
	int ey = p[1].first;
	int ex = p[1].second;
	find(fy, fx, ey, ex);
	return;
	}
	for (int i = begin + 1; i < v.size(); ++i) {
	p.push_back(v[i]);
	solve(p,i);
	p.pop_back();
	}
	}
	int main()
	{
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < m; ++j) {
	cin >> a[i][j];
	if (a[i][j] == '#')
	v.push_back({ i,j });
	}
	vector<pair<int, int>> p;
	solve(p,-1);
	cout << ans << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub