글 읽기 - 2186 문자판 질문입니다!

lsy173 2년 전 0

BFS 로 풀었고, 주어진 테스트 케이스에 대해선 통과 했습니다!

어떤 조건을 빠트렸길래 어떤 테스트 케이스에서 틀리는지 너무 궁금해서 질문 올립니다ㅠㅠ

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <utility>
using namespace std;

char alphabet[102][102];
int path[102][102];
bool check[102][102];
char word[82];
int wordcnt=0, wordlen;
int dx[4] = { 0, -1, 0, 1 };
int dy[4] = { 1, 0, -1, 0 };
int N, M, K;
int endpath=0;

bool bfs(int x, int y)
{
	queue<pair<int, int>> q;
	bool found = false;
	bool next = false;
	check[x][y] = true;
	q.push(make_pair(x, y));
	while (!q.empty())
	{
		next = false;
		pair<int, int> coordinate = q.front();
		q.pop();
		for (int k = 1; k <= K; k++)
		{
			for (int i = 0; i < 4; i++)
			{
				if (0 <= coordinate.first + k*dx[i] && coordinate.first + k*dx[i] <= N - 1 && 0 <= coordinate.second + k*dy[i] && coordinate.second + k*dy[i] <= M - 1)
				{
					if (check[coordinate.first + k*dx[i]][coordinate.second + k*dy[i]] == false && word[wordcnt] == alphabet[coordinate.first + k*dx[i]][coordinate.second + k*dy[i]])
					{
						check[coordinate.first + k*dx[i]][coordinate.second + k*dy[i]] = true;
						path[coordinate.first + k*dx[i]][coordinate.second + k*dy[i]] = path[coordinate.first][coordinate.second] + 1;
						q.push(make_pair(coordinate.first + k*dx[i], coordinate.second + k*dy[i]));
						if(word[wordcnt] == alphabet[coordinate.first + k*dx[i]][coordinate.second + k*dy[i]])
							wordcnt++;
						if (wordcnt == wordlen - 1) // reach the end.
						{
							endpath = path[coordinate.first + k*dx[i]][coordinate.second + k*dy[i]];
							found = true;
						}
					}
				}
			}
		}
		
	}
	// if search finished, return true.
	// or, return false.
	return found;
}

int main(void)
{
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 0; i < N; i++)
		scanf("%s", alphabet[i]);
	memset(check, false, sizeof(check));
	memset(path, 0, sizeof(path));
	memset(word, '\0', sizeof(word));
	scanf("%s", word);
	wordlen = strlen(word);
	
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M;j++)
			if (alphabet[i][j] == word[0])
			{
				wordcnt++;
				bool found = bfs(i, j);
				if (found == true)
					break;
				else
					wordcnt = 0;
			}
	printf("%d\n", endpath);
	return 0;
}

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

문제

문제

출처

ACM-ICPC

2186 문자판 질문입니다!

lsy173 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말