글 읽기 - 반례좀 부탁드립니다 ㅜㅜ

parkerk4 3년 전 0

예제랑 질문리스트에 있는 테스트 케이스들 다 통과했는데

어디가 문제인지 모르겠네요 ㅜㅜ

#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <assert.h>
#include <climits>

class Solution {
public:
	Solution(int m, int n, int dist) : _m(m), _n(n), _dist(dist) {}

	int MaxDefence(std::vector<std::vector<bool>> map) {
		int max_val = 0;
		for (int i = 0; i < _n - 2; ++i) {
			for (int j = i+1; j < _n - 1; ++j) {
				for (int k = j+1; k < _n; ++k) {
					max_val = std::max(max_val, Defence(map, i, j, k));
				}
			}
		}
		return max_val;
	}

	int Defence(std::vector<std::vector<bool>> map, int pos1, int pos2, int pos3) {
		std::vector<std::vector<bool>> new_map = map;
		
		int res = 0;
		for (int i = 0; i < _m; ++i) {
			res += Calculate(new_map, pos1, pos2, pos3);
			new_map = Update(new_map);
		}
		
		return res;
	}

	int Calculate(std::vector<std::vector<bool>>& map, int pos1, int pos2, int pos3) {
		int min_dist1 = INT_MAX;
		int min_dist2 = INT_MAX;
		int min_dist3 = INT_MAX;
		int row1 = _m , col1 = _n;
		int row2 = _m , col2 = _n;
		int row3 = _m , col3 = _n;

		for (int i = _m - 1; i >= 0; --i) {
			for (int j = _n - 1; j >= 0; --j) {
				if (!map[i][j]) {
					continue;
				}
				int dist1 = _m - i + std::abs(j - pos1);
				if (dist1 <= _dist && dist1 <= min_dist1) {
					min_dist1 = dist1;					
					if (j <= col1) {
						row1 = i;
						col1 = j;
					}					
				}
				int dist2 = _m - i + std::abs(j - pos2);
				if (dist2 <= _dist && dist2 <= min_dist2) {
					min_dist2 = dist2;
					if (j <= col2) {
						row2 = i;
						col2 = j;
					}
				}
				int dist3 = _m - i + std::abs(j - pos3);
				if (dist3 <= _dist && dist3 <= min_dist3) {
					min_dist3 = dist3;
					if (j <= col3) {
						row3 = i;
						col3 = j;
					}
				}
			}
		}


		auto is_same = [](int r1, int c1, int r2, int c2) {
			if (r1 == r2 && c1 == c2) return true;
			return false;
		};
		
		int res = 0;
		if (min_dist1 != INT_MAX) {
			res++;
			map[row1][col1] = false;
		}

		if (min_dist2 != INT_MAX &&
			(min_dist1 == INT_MAX || !is_same(row1, col1, row2, col2))) {
			res++;
			map[row2][col2] = false;
		}

		if (min_dist3 != INT_MAX && 
			(min_dist1 == INT_MAX || !is_same(row1, col1, row3, col3)) &&
			(min_dist2 == INT_MAX || !is_same(row2, col2, row3, col3))) {
			res++;
			map[row3][col3] = false;
		}

		return res;
	}

	std::vector<std::vector<bool>> Update(const std::vector<std::vector<bool>>& map) {
		std::vector<std::vector<bool>> new_map(_m, std::vector<bool>(_n, false));
		for (int i = 0; i < _m - 1; ++i) {
			new_map[i + 1] = map[i];
		}
		return new_map;
	}
	
	void print(const std::vector<std::vector<bool>>& map) {
		for (int i = 0; i < _m; ++i) {
			for (int j = 0; j < _n; ++j) {
				std::cout << map[i][j] << ' ';
			}
			std::cout << std::endl;
		}
		std::cout << std::endl;
	}

private:
	int _m, _n, _dist;
};

int main()
{
	int m, n, dist;
	std::cin >> m >> n >> dist;

	std::vector<std::vector<bool>> map(m, std::vector<bool>(n,false));
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < n; ++j) {
			char a;
			std::cin >> a;
			map[i][j] = a == '1' ? true : false;
		}
	}

	Solution s(m, n, dist);
	std::cout<<s.MaxDefence(map)<<std::endl;

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례좀 부탁드립니다 ㅜㅜ

parkerk4 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말