글 읽기 - 고수분들 반례좀 찾아주세요..

ssh202 4년 전 0

테스트 케이스는 모두 맞는데 제출하자마자 틀렸다고 나오네요...

반례좀 찾아주실수 있을까요??

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int n;
int map[21][21] = { 0, };
int nmap[21][21] = { 0, };
int dx[] = { 0, 1, 1, 1, 1 };
int dy[] = { 0,-1,1,1,-1 };
int dr[] = { 0,0,-1,1 };
int dc[] = { -1,1,0,0 };

int ans = -1;



void bfs(int i, int j, int group) {
	queue<pair<int, int>> q;
	q.push({ i,j });
	nmap[i][j] = group;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dr[i];
			int ny = y + dc[i];
			if (nx > 0 && ny > 0 && nx <= n && ny <= n && nmap[nx][ny] == -1) {

				nmap[nx][ny] = group;
				q.push({ nx,ny });
			}
		}
	}
}





/*bool check(int x, int y, int d1, int d2) {


if ((x + d1) > n) return false;
if ((y - d1) <= 0) return false;
if ((x + d2) >= n) return false;
if (y + d2 >= n) return false;
if (((x + d1 + d1) > n) || ((y - d1 + d1)<=0) || ((y - d1 + d1) > n)) return false;
return true;
}*/

void cal_1(int x, int y, int d1, int d2) {


	int tx = x;
	int ty = y;
	nmap[tx][ty] = 5;
	tx--;
	while (tx >= 1) {

		nmap[tx][ty] = 1;
		tx--;
	}
	tx = x;
	while (d1--) {
		tx = tx + dx[1];
		ty = ty + dy[1];
		nmap[tx][ty] = 5;
	}
	ty--;
	while (ty >= 1) {

		nmap[tx][ty] = 3;
		ty--;
	}

}

void cal_2(int x, int y, int d1, int d2) {

	int tx = x;
	int ty = y;
	nmap[tx][ty] = 5;
	while (d2--) {
		tx = tx + dx[2];
		ty = ty + dy[2];
		nmap[tx][ty] = 5;
	}
	ty++;
	while (ty <= n) {
		nmap[tx][ty] = 2;
		ty++;
	}

}
void cal_3(int x, int y, int d1, int d2) {

	int tx = x + d1;
	int ty = y - d1;
	nmap[tx][ty] = 5;
	while (d2--) {
		tx = tx + dx[3];
		ty = ty + dy[3];
		nmap[tx][ty] = 5;
	}
	tx++;
	while (tx <= n) {

		nmap[tx][ty] = 4;
		tx++;
	}

}
void cal_4(int x, int y, int d1, int d2) {

	int tx = x + d2;
	int ty = y + d2;
	nmap[tx][ty] = 5;
	while (d1--) {
		tx = tx + dx[4];
		ty = ty + dy[4];
		nmap[tx][ty] = 5;
	}
	tx++;
	while (tx <= n) {

		nmap[tx][ty] = 4;
		tx++;
	}

}


void cal(int x, int y, int d1, int d2) {
	if (true) {
		memset(nmap, -1, sizeof(nmap));
		//memset(checker, false, sizeof(checker));
		cal_1(x, y, d1, d2);
		cal_2(x, y, d1, d2);
		cal_3(x, y, d1, d2);
		cal_4(x, y, d1, d2);
		bfs(1, 1, 1);
		bfs(1, n, 2);
		bfs(n, 1, 3);
		bfs(n, n, 4);
		bfs(x + 1, y, 5);
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (nmap[i][j] == -1) nmap[i][j] = 5;
			}
		}
		int num[5] = { 0, };
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (nmap[i][j] == 1) {
					num[0] += map[i][j];
				}
				else if (nmap[i][j] == 2) {
					num[1] += map[i][j];
				}
				else if (nmap[i][j] == 3) {
					num[2] += map[i][j];
				}
				else if (nmap[i][j] == 4) {
					num[3] += map[i][j];
				}
				else {
					num[4] += map[i][j];
				}
			}
		}

		sort(num, num + 5);
		int temp = num[4] - num[0];
		if (ans == -1 || ans > temp) {
			ans = temp;
		}


	}
}



int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 1; i <= n - 2; i++) {
		for (int j = 2; j <= n - 1; j++) {
			for (int d1 = 1; d1 <= n - i - 1 && d1 <= j - 1; d1++) {
				for (int d2 = 1; d2 <= n - i - 1 && d2 <= n - j; d2++) {
					cal(i, j, d1, d2);
				}
			}
		}
	}
	if (ans == -1) {
		cout << 0;
		return 0;
	}
	cout << ans << endl;;
	return 0;
}

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

문제

문제

출처

ICPC

고수분들 반례좀 찾아주세요..

ssh202 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말