#include # define MAXRC 750 # define MAXD 375 using namespace std; /* 0. 최대 행,열이 750 이므로 다이아몬드의 최대 크기는 375 (374 일수도) 750*750*372 = 약 2억1천이니까 되지 않을까? 1. 우선 dp의 저장 방식은 현재 탐색하려는 크기 x일 때, (x-1)크기 후보가 상,하,좌,우에 있는지 저장한다. (class Diamond 참고) 1-1. 자신의 크기를 x크기라고 해보자. 자신의 위치 (i,j)로부터 상,하,좌,우에 (x-1) 크기의 후보가 될만한 것이 있다면 자신의 dp에 저장한다. 예를 들어, dp[i][j]에 현재 크기 x일 떄 (x-1)크기의 후보가 좌,상 이 있다면 다음과 같이 저장한다. dp[i][j].up = x-1; dp[i][j].left = x-1; 1-2. 초기 후보 (크기가 2일 때)는 크기가 1일 때 후보를 봐야하는데, 그냥 상,하,좌,우에 실제로 있는지만 보면 된다. 상,좌에만 있다면 다음과 같이 저장한다. dp[i][j].up = 1; dp[i][j].left = 1; 1-3. 만약 상,하,좌,우 후보 4개가 동시에 존재한다면, 크기 x의 다이아몬드가 존재한다. 2. dp 에는 이전 크기의 후보만 저장되어있다. 이를 통해서 어떻게 현재 x 크기의 후보라고 말할 수 있는가? 2-1. 현재 x크기의 "상" 후보군이 되려면, 이전의 상+좌+우 후보 2-2. 현재 x크기의 "하" 후보군이 되려면, 이전의 하+좌+우 후보 2-3. 현재 x크기의 "좌" 후보군이 되려면, 이전의 좌+상+하 후보 2-4. 현재 x크기의 "우" 후보군이 되려면, 이전의 우+상+하 후보 3. (i,j) 의 위치는 크기 x의 후보이면서 y의 후보일 수도 있다. 그러므로 3차원 배열로 관리하는것이 편할듯 하다. => 메모리땜에 안될듯 3-1. 그러면 어차피 이전 정보만 필요하니까 750*750짜리 배열 2개 선언해서 번갈아가면서 하는식으로? */ class Diamond { public: int up; int down; int left; int right; Diamond() { this->up = 0; this->down = 0; this->left = 0; this->right = 0; } Diamond(int u, int d, int l, int r) { this->up = u; this->down = d; this->left = l; this->right = r; } //상,하,좌,우 순서로 bitmask처럼 return int candidate() { int num = 0; if (this->up) num += (1<<3); if (this->down) num += (1<<2); if (this->left) num += (1<<1); if (this->right) num += 1; return (num); } }; string mine[MAXRC+1]; //입력 광산 Diamond dp1[MAXRC+1][MAXRC+1]; Diamond dp2[MAXRC+1][MAXRC+1]; Diamond (*prev_dp)[MAXRC+1] = dp1; //실제 dp연산에서 이전값 Diamond (*cur_dp)[MAXRC+1] = dp2; //실제 dp연산에서 현재값 int maxdiamond = 0; //answer: 가장 큰 다이아몬드 size //size=x의 diamond및 diamond후보군 탐색 void search_sizeX_diamond(int x, int r, int c) { //prev_dp를 토대로 cur_dp값 갱신 for(int i=0; i0 && (prev_dp[i-1][j].candidate()&8)==8) && (j>0 && (prev_dp[i][j-1].candidate()&2)==2) && (j0 && (prev_dp[i][j-1].candidate()&2)==2) && (j0 && (prev_dp[i][j-1].candidate()&2)==2) && (i>0 && (prev_dp[i-1][j].candidate()&8)==8) && (i0 && (prev_dp[i-1][j].candidate()&8)==8) && (i> r >> c; for(int i=0; i> mine[i]; //1-2. 초기 후보 dp 할당 for(int i=0; i

제출 #192175

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: