#include <iostream>usingnamespacestd;staticintN=0;staticintM=-1;staticintword_map[50][50]={0,};staticintmax_length=0;intFindDiamond(intidx,intjdx,intmax_depth){//idx, jdx부터 아래로 만들어지는 다이아몬드를 찾으면 최대 길이를, 못찾으면 -1을 반환한다.if(word_map[idx][jdx]==0)return-1;intdepth=1;intmid=0;if(max_depth%2==0)mid=max_depth/2;elsemid=max_depth/2+1;intbegin=-1,end=1;intflag=1;while(depth<mid&&flag==1){for(inti=(jdx+begin);i<=(jdx+end);i++){if(word_map[depth][i]==0){flag=0;break;}}depth++;begin--;end++;}if(flag==0)return-1;begin++;end--;while(depth>=mid&&begin<end&&flag==1){for(inti=(jdx+begin);i<=(jdx+end);i++){if(word_map[depth][i]==0){flag=0;break;}}depth++;begin++;end--;}returndepth;//depth만큼이 다이아몬드의 최대길이가 되지.}intmain(void){intC=0;cin>>C;while(C-->0){max_length=0;cin>>N;getchar();introw_cnt=0;intword_cnt=0;while(row_cnt<N){charch=getchar();if(ch==10){word_cnt=0;row_cnt++;continue;}if(ch=='#')word_map[row_cnt][word_cnt]=1;word_cnt++;if(word_cnt>M)M=word_cnt;}for(inti=0;i<N;i++){for(intj=0;j<M;j++){for(intk=N-i;k>0;k--){intlength=FindDiamond(i,j,k);if(length>max_length)max_length=length;}}}cout<<max_length<<endl;}return0;}
ginger
제가 구현한 알고리즘은 정말 간단합니다!
idx, jdx부터 max_depth까지 정말 나이브하게 다이아몬드 탐색을 해서 최대 길이를 잽니다.
시간도 여유있게 들어가구요... 근데 오답이 자꾸 뜨네요 ㅋㅋ
테스트 케이스 외에도 다음과 같은 테스트도 해봤는데 잘 되서... 난감합니다. ㅠㅠ
(사실 몇가지로 더 실험해봤는데 잘 되더군요..)
6
3
...
...
...
4
#..#
#..#
#..#
.##.
4
....
.##.
####
.##.
4
#.#.
.#.#
.##.
#..#
3
..#.
.###
..#.
5
#####
#####
#####
#####
#####
도움이 필요합니다. 고수님들!
빠트린 부분이 어느 부분일까요?!
10년 전