로곡 P1003 문제풀이(50분 코드)

9231 단어

로곡 P1003 문제풀이(50분 코드)

  • 제목설명
  • 분석
  • 코드
  • 요약

    • 제목 설명


    독특한 시상식을 준비하기 위해 주최자는 회의장의 직사각형 구역(평면 직각 좌표계의 첫 번째 상한으로 볼 수 있음)에 직사각형 카펫을 깔았다.모두 n장의 카펫이 있는데, 번호는 1부터 n까지이다.이제 이 카펫들을 번호에 따라 작은 순서에서 큰 순서로 좌표축에 평행으로 깔고, 뒤에 깔린 카펫은 앞에 깔린 카펫 위에 덮는다.카펫을 설치한 후, 조직자는 지면의 어떤 점을 덮은 맨 위에 있는 카펫의 번호를 알고 싶어 한다.주의: 직사각형 카펫의 경계와 네 개의 정점에 있는 점도 카펫으로 덮인 셈이다.입력 형식 총 n+2줄을 입력합니다.첫 번째 줄은 모두 n장의 카펫이 있음을 나타내는 정수 n이다.다음 n줄에서 i+1줄은 번호 i의 카펫을 표시하는 정보로 네 개의 정수 a, b, g, k를 포함하고 두 정수 사이를 빈칸으로 구분하여 카펫의 왼쪽 하단에 설치된 좌표(a, b)와 카펫이 x축과 y축 방향의 길이를 나타낸다.n+2행은 두 개의 정수 x와 y를 포함하고 원하는 지면의 점의 좌표(x, y)를 나타낸다.출력 형식은 총 1줄, 정수로 원하는 카펫의 번호를 나타낸다.여기에 카펫이 덮여 있지 않으면 출력-1입니다.
    [데이터 범위] 30%의 데이터에 대해 n≤2가 있다.
    50%의 데이터에 대해 0≤a, b, g, k≤1000.
    100%의 데이터에 대해 0≤n≤104, 0≤a, b, g, k≤105가 있다.

    분석하다.


    이 문제는 수조로 염색하는 방법으로 할 수 있다. 수조 중 어느 한 범위 내의 모든 숫자를 양탄자 번호로 염색하고 마지막으로 목표 위치의 양탄자 번호를 출력하면 된다.(데이터 범위를 고려하지 않음)

    코드

    #include
#include
#include
#include
#include
using namespace std;
int map[2020][2020];
int n,x,y;
struct cpt{
  int x,y,h,v;//    a,b,g,k           x y              
};    //          ，      
cpt a[101000];
void init(){
  cin>>n;
  memset(map,-1,sizeof(map)); 
  for(int i=1;i<=n;i++){
    cin>>a[i].x>>a[i].y>>a[i].h>>a[i].v;
  }
  cin>>x>>y;
  return;
}
void cv(int pos){
  for(int i=a[pos].x;i<=a[pos].x+a[pos].h;i++){
    for(int j=a[pos].y;j<=a[pos].y+a[pos].v;j++){
   map[i][j]=pos;
 }
  }
  return;
}
int main(){
  
  init();
  for(int i=1;i<=n;i++){cv(n);}
  cout<<map[x][y]<<"
    "    ;
  
  return 0;
}

    총결산


    이렇게 제출하면 50점을 받을 수 있다. 왜냐하면 50%의 데이터(주로 a, b, g, k)는 수조에 넣을 수 있고 나머지 50%의 데이터는 2차원 수조의 최대 범위를 넘어설 수 있으며 2차원 수조는 데이터 범위를 만족시키는 크기로 갈 수 없기 때문이다.그래서 만점 코드는 2차원수조 염색법으로 할 수 없다.
    210110 | 백준 백트래킹 15649 | C++
    swift 따위와 구조체

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage