글 읽기 - 저의 알고리즘이 틀린 이유가 궁금합니다.

sdf3265 5년 전 0

아래와 같이 알고리즘을 구성하였으나, 틀렸다고 나오기에

너무 답답해서 질문드립니다.

무엇이 잘못되었는지 지적해주시면 감사하겠습니다.

#include<iostream>
#include<cstdio>
using namespace std;

int r, c;
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };
char a[21][21];
bool check[100];
int ans; 


void dfs(int x, int y,int cnt) {
	if (cnt > ans) ans = cnt;

	for (int k = 0; k < 4; k++) {
		int nx = x + dx[k];
		int ny = y + dy[k];

		if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
			if (check[a[nx][ny] - 'A'] == false) {
				check[a[nx][ny] - 'A'] = true;
				dfs(nx, ny, cnt+1);
				check[a[nx][ny] - 'A'] = false;
			}

		}
	}
}
int main() {

	cin >> r >> c;

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			scanf("%1c", &a[i][j]);

		}
	}
	dfs(0, 0,1);

	cout << ans << endl;
	return 0;
}

movie_jo 5년 전 0

"말이 지나는 칸은 좌측 상단의 칸도 포함된다."

djm03178 5년 전 0

예제가 나온 건 정말 너무나도 우연으로 나온 것입니다. 부디 질문을 올리기 전에 다양한 케이스를 시도해보고 올려주세요.

scanf("%1c")는 공백과 개행 문자까지 모두 입력받습니다. 애초에 입력도 제대로 못 받는 코드입니다. scanf(" %1c") 처럼 % 앞에 공백을 하나 두거나, 그냥 cin으로 입력받으면 됩니다.
좌측 상단의 칸의 알파벳에 대한 방문 처리를 하지 않아서 다른 칸에 좌측 상단과 같은 알파벳이 있어도 방문하게 됩니다.

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

문제

문제

출처

ICPC

저의 알고리즘이 틀린 이유가 궁금합니다.

sdf3265 5년 전 0

movie_jo 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말