CCF 201912 - 2 휴지통 입지 선정 (100 점)

(1) 제목 설명
(2) 알고리즘 사상
4. 567917. 여기 서 이산 점 을 지정 합 니 다. 각 점 간 의 관 계 를 판단 해 야 하기 때문에 점 의 좌표 만 저장 하고 해당 하 는 그림 을 구성 하지 않 아 도 되 며 메모리 제한 을 고려 하지 않 아 도 됩 니 다
4. 567917. 그 후에 각 점 간 의 관계 와 득점 규칙 을 고려 해 야 한다. 각 점 간 의 관 계 는 인접 과 대각선 두 가지 로 나 뉘 고 4 가지 인접 을 만족 시 켜 야 회수 소 를 설립 하고 점 수 를 계산 하 는 것 을 고려 할 수 있다.대각선 관 계 는 휴지통 을 설치 한 후에 점수 기준 으로 시작 하고 대각선 쓰레기 점 1 개 는 1 점 에 대응 합 니 다
4. 567917. 상기 규칙 에 따라 점 수 를 계산 하기 시작 하고 매번 에 대응 하 는 관계 의 두 가 지 를 동시에 가산 점 을 하여 순환 횟수 를 줄 일 수 있다
(3) 코드 구현
#include
#include
using namespace std;

struct node {
     
	int x;
	int y;
	int grade;
	int tempgrade;
	node() {
     
		x=y=0;
		grade=-4;
		tempgrade=0;
	}
};

inline bool nextto(node pos1, node pos2) {
     
	if(pos1.x==pos2.x && abs(pos1.y-pos2.y)==1)
		return true;
	else if(pos1.y==pos2.y && abs(pos1.x-pos2.x)==1)
		return true;
	return false;
}

inline bool diagonal(node pos1, node pos2) {
     
	if(abs(pos1.x-pos2.x)==1 && abs(pos1.y-pos2.y)==1)
		return true;
	return false;
}

int main() {
     
	int n;
	cin>>n;
	int a[5]= {
     0};
	node pos[n];
	for(int i=0; i<n; i++)
		cin>>pos[i].x>>pos[i].y;
	for(int i=0; i<n-1; i++) {
     
		for(int j=i+1; j<n; j++) {
     
			if(nextto(pos[i],pos[j])) {
     
				pos[i].grade++;
				pos[j].grade++;
			}
			if(diagonal(pos[i],pos[j])) {
     
				pos[i].tempgrade++;
				pos[j].tempgrade++;
			}
		}
		if(pos[i].grade==0) {
     
			pos[i].grade+=pos[i].tempgrade;
		}
	}
	for(int i=0; i<n; i++) {
     
		if(pos[i].grade>=0)
			a[pos[i].grade]++;
	}
	for(int i=0; i<5; i++)
		cout<<a[i]<<endl;
	return 0;
}

좋은 웹페이지 즐겨찾기