제출 #503069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
503069		bang627	보물 찾기 (CEOI13_treasure2)	C++14	0 / 100	13 ms	484 KiB

treasure

#include "treasure.h"
#include <iostream>

using namespace std;
void solution(int x1, int y1, int x2, int y2, int** board);
void findTreasure (int N) {
    int** board = new int* [N];
    for (int i = 0; i < N; i++) board[i] = new int [N];
    solution(1, 1, N, N, board);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << board[i][j] << " ";
            if (board[i][j] == 1) Report(i + 1, j + 1);
        }
        cout << endl;
    }
    //if(cnt > 0) Report (1, 1);
}
void solution(int x1, int y1, int x2, int y2,int **board) {
    cout << x1 << " " << y1 << "~" << x2 << " " << y2 << endl;
    int dx = x2 - x1 + 1, dy = y2 - y1 + 1;
    int cnt1 = countTreasure(x1, y1, x2, y2);
    if (cnt1 == 0) {
        for (int i = x1; i <= x2; i++) for (int j = y1; j <= y2; j++) board[i - 1][j - 1] = 0;
        return;
    }
    if (cnt1 == dx * dy) {
        for (int i = x1; i <= x2; i++) for (int j = y1; j <= y2; j++) board[i - 1][j - 1] = 1;
        return;
    }
    if (dx >= dy) {
        int mx = int((x1 + x2) / 2);
        int cnt2 = countTreasure(x1, y1, mx, y2);        
        int cnt3 = cnt1 - cnt2;
        if (cnt2 == 0) for (int i = x1; i <= mx; i++) for (int j = y1; j <= y2; j++) board[i - 1][j - 1] = 0;
        else if (cnt2 == (mx - x1 + 1) * dy) for (int i = x1; i <= mx; i++) for (int j = y1; j <= y2; j++) board[i - 1][j - 1] = 1;
        else solution(x1, y1, mx, y2,board);

        if (cnt3 == 0) for (int i = mx + 1; i<=x2; i++) for (int j = y1; j <= y2; j++) board[i - 1][j - 1] = 0;
        else if (cnt3 == (x2-mx) * dy) for (int i = mx + 1; i <= x2; i++) for (int j = y1; j <= y2; j++) board[i - 1][j - 1] = 1;
        else solution(mx+1, y1, x2, y2,board);
    }
    else {
        int my = int((y1 + y2) / 2);
        int cnt2 = countTreasure(x1, y1, x2, my);
        int cnt3 = cnt1 - cnt2;
        if (cnt2 == 0) for (int i = x1; i <= x2; i++) for (int j = y1; j <= my; j++) board[i - 1][j - 1] = 0;
        else if (cnt2 == (my- y1 + 1) * dx) for (int i = x1; i <= x2; i++) for (int j = y1; j <= my; j++) board[i - 1][j - 1] = 1;
        else solution(x1, y1, x2, my, board);

        if (cnt3 == 0) for (int i = x1; i <= x2; i++) for (int j = my+1; j <= y2; j++) board[i - 1][j - 1] = 0;
        else if (cnt3 == (y2-my) * dx) for (int i = x1; i <= x2; i++) for (int j = my+1; j <= y2; j++) board[i - 1][j - 1] = 1;
        else solution(x1, my+1, x2, y2, board);
    }
}

• Subtask 1: 0 / 100