글 읽기 - 이 문제 백트래킹으로 짰는데 81퍼에서 틀리네요

juhongkim2 7년 전 0

오목하듯이 풀었습니다.

그런데 81퍼센트에서 틀리네요...

어디서 틀린걸까요?

추가

도저히 안풀려서 알고리즘 분류 보니까

백트래킹도 아니고 그냥 배열이네요

방향배열 만들어서 3중포문 돌리니까 답은 나오는데 왜 백트래킹으로 하면 틀리는걸까요

오목이랑 이 문제랑 같은 문자(돌)을 연속으로 5개 잇느냐 3개 잇느냐 차이밖에 없는거 같은데

풀이가 완전히 다르니...

#include <stdio.h>

char win,map[50][50];
int N,flag,cnt,check[50][50];

int IsinRange(int x, int y)
{
	if(x<0 || y<0 || x>=N || y>=N)
		return 0;

	return 1;
}

void Reset(int x, int y)
{
	int i,j;

	if(cnt==3){
		flag=1;
		win=map[y][x];
		return;
	}

	cnt=0;

	for(i=0;i<N;i++){
		for(j=0;j<N;j++){
			check[i][j]=0;
		}
	}
}

void V(int x, int y)
{
	if(check[y][x]==1 || IsinRange(x,y)==0)
		return;

	check[y][x]=1;
	cnt++;

	if(map[y+1][x]==map[y][x])
		V(x,y+1);
	if(map[y-1][x]==map[y][x])
		V(x,y-1);
}

void H(int x, int y)
{
	if(check[y][x]==1 || IsinRange(x,y)==0)
		return;

	check[y][x]=1;
	cnt++;

	if(map[y][x+1]==map[y][x])
		V(x+1,y);
	if(map[y][x-1]==map[y][x])
		V(x-1,y);
}

void DL(int x, int y)
{
	if(check[y][x]==1 || IsinRange(x,y)==0)
		return;

	check[y][x]=1;
	cnt++;

	if(map[y+1][x+1]==map[y][x])
		V(x+1,y+1);
	if(map[y-1][x-1]==map[y][x])
		V(x-1,y-1);
}

void DR(int x, int y)
{
	if(check[y][x]==1 || IsinRange(x,y)==0)
		return;

	check[y][x]=1;
	cnt++;

	if(map[y-1][x+1]==map[y][x])
		V(x+1,y-1);
	if(map[y+1][x-1]==map[y][x])
		V(x-1,y+1);
}

void Go(int x, int y)
{
	V(x,y);
	Reset(x,y);
	if(flag==1)
		return;

	H(x,y);
	Reset(x,y);
	if(flag==1)
		return;

	DL(x,y);
	Reset(x,y);
	if(flag==1)
		return;

	DR(x,y);
	Reset(x,y);
	if(flag==1)
		return;
}

int main()
{
	int i,j;

	scanf("%d",&N);

	for(i=0;i<N;i++){
		for(j=0;j<N;j++){
			scanf(" %c", &map[i][j]);
		}
	}

	for(i=0;i<N;i++){
		for(j=0;j<N;j++){
			if(check[i][j]==0 && map[i][j]!='.')
				Go(j,i);
		}
	}

	if(flag==1)
		printf("%c\n",win);
	else
		printf("ongoing\n");

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이 문제 백트래킹으로 짰는데 81퍼에서 틀리네요

juhongkim2 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말