7개의 댓글이 있습니다.
-
-
Taeyoon_Lee -
오타 발견. "1, 7 중 하나입니다."가 아니라 "1, 4 중 하나입니다." 인 것 같네요.
16년 전 link
-
-
-
Megalusion -
제 소스입니다.
[code]
#include
#include
#include
#include
using namespace std;
char a[101][101];
int c[101][101];
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
vectornum[10];
vectortype;
vectorfour;
int n,m;
void go(int x, int y){
int mask=0;
int cnt=0;
for(int k=0; k<4; k++){
if(x+dx[k]>=1 && x+dx[k]<=n && y+dy[k]>=1 && y+dy[k]<=m){
if(a[x+dx[k]][y+dy[k]] == '*'){
cnt++ ;
mask = mask + (1<
}
}
if(cnt>=2 && mask!=5 && mask!=10){
type.push_back(mask);
}
for(int k=0; k<4; k++){
if(x+dx[k]>=1 && x+dx[k]<=n && y+dy[k]>=1 && y+dy[k]<=m){
if(a[x+dx[k]][y+dy[k]] == '*'){
if(c[x+dx[k]][y+dy[k]]==0){
c[x+dx[k]][y+dy[k]] = 1;
go(x+dx[k],y+dy[k]);
}
}
}
}
}
int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int t;
num[0].push_back(3);num[0].push_back(6);num[0].push_back(12);num[0].push_back(9);
num[2].push_back(6);num[2].push_back(12);num[2].push_back(3);num[2].push_back(9);
num[3].push_back(6);num[3].push_back(14);num[3].push_back(12);
num[4].push_back(9);num[4].push_back(14);four.push_back(14);four.push_back(9);
num[5].push_back(3);num[5].push_back(9);num[5].push_back(6);num[5].push_back(12);
num[6].push_back(3);num[6].push_back(11);num[6].push_back(6);num[6].push_back(12);num[6].push_back(9);
num[7].push_back(6);
num[8].push_back(3);num[8].push_back(6);num[8].push_back(14);num[8].push_back(12);num[8].push_back(9);num[8].push_back(11);
num[9].push_back(3);num[9].push_back(6);num[9].push_back(14);num[9].push_back(12);num[9].push_back(9);
scanf("%d\n",&t);
while(t--){
scanf("%d %d\n",&n,&m);
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
for(int i=1; i<=n; i++)
scanf("%s\n",a[i]+1);
int ans=0;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(a[i][j]=='*' && c[i][j] == 0){
c[i][j] = 1;
type.clear();
go(i,j);
bool ch = false;
for(int i=0; i<=9; i++){
if(type == num[i]){
ch = true;
ans += i;
}
}
if(ch == false && type==four)
ans += 4;
}
}
}
printf("%d\n",ans);
}
return 0;
}
[/code]
16년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Being
안녕하세요. D번 setter ryuwonha(beingryu) 입니다.
이 문제의 비화를 전하자면, 사실 모의고사를 준비할 때 각 사람마다 쉬운 문제 하나, 어려운 문제 하나씩을 가지고 모이기로 했었습니다. 그런데 제가 들고 온 쉬운 문제가 바로 이 문제였고, 어려운 문제는 다른 문제여서 출제진에게 이게 어째서 쉬운 문제냐 ㅇ<-< 라고 구박을 들었더랬습니다 ㅠ.ㅠ 사실 두 문제 다 생각보다는 어렵지 않은 데 말이지요. fastest로 푼 Gumx 팀을 보면 더더욱 알 수 있습니다.
이 문제를 푸는 방법은 특정히 어떤 알고리즘을 요구한 것이 아니기 때문에 당연히 매우 여러 가지가 존재합니다. 여기서는 두 가지 approach 정도를 설명해 보겠습니다.
1. 탐색의 순서를 고정한 DFS (Gumx 팀 등의 풀이)
상당히 깔끔하게 구현할 수 있는 풀이입니다. 기본적인 아이디어는, 어떤 탐색되지 않은 검은 색 격자가 최초로 등장할 경우 임의로 정한 탐색 순서에 따라서(즉 Monte Carlo method처럼 탐색 순서를 매번 다르게 정하는 것이 아니라, 이를테면 상하좌우의 순서대로 방문하게 합니다. 그리고 방문하는 칸들을 두 종류로 나누는데, 각각 꼭지점과 중간점이라 칭합시다. 중간점은 그야말로 선분을 늘림으로써 생긴 의미 없는 점들이라, 이 점들을 결국엔 제거한다고 생각하면 됩니다. 그러면 이러한 중간점은,
#@#
#
@
#
위의 그림에서 @로 표시된 칸들과 같이, 다른 점들과는 연결되지 않고 좌우/상하로만 연결된 격자라고 할 수 있겠지요. 이렇지 않은 격자(=꼭지점)을 탐색하는 순서대로 각 꼭지점이 어떻게 상하좌우로 연결되어 있는지 리스트에 집어넣는다고 칩시다.
탐색 순서를 상하좌우의 순서라고 할 때, 0이라는 문자는 항상
하우 / 상우 / 상좌 / 하좌
와 같이 연결된 네 개의 꼭지점을 순서대로 탐색하게 됩니다. 길이를 얼마를 늘렸던지 간에 말이죠. 이와 같이 0-9까지의 패턴을 precode한 후 대조하여 풀면 됩니다.
2. case-by-case search
한편, 위와 같은 탐색은 일반적인 비슷한 모양 문자에 대해서 적용할 수 있는 반면 dfs로 탐색하지 않고 경우를 나누어 푸는 방법도 있을 수 있겠습니다. 예를 들어 위에서와 같이 검은 색 격자를 최초로 발견했다고 칩시다. 그렇다면 그 격자는 그 문자에 대해 가장 왼쪽 위의 격자가 됩니다.
그렇다면 그 격자에서 오른쪽으로 연결되어 있다면 그 문자는 0, 2, 3, 5, 6, 7, 8, 9 중 하나입니다. 그렇지 않다면 1, 4 중 하나입니다.
이와 같이 코드 내에서 적당한 깊이의 분기문과 기준을 삼으면 위와 같은 briliant idea 없이도 쉽게 풀 수 있습니다. 다만, 각 케이스에 대한 검증을 확실히 해야 할 것입니다.
코드는 지금 자리에 준비되지 않았네요. 다음에 준비되면 다시 업로드할게요.
16년 전