글 읽기 - 시간초과 도와주세요

sj7699 5년 전 0

처음엔 bfs로 풀어서 시간초과가 났습니다. 그래서 dp와 dfs로 풀려고 했는데 시간초과가 또 나네요....

제가 dp를 엉망으로 사용한건가요?

#include<iostream>
#include<string>
#include<vector>
using namespace std;
char arr[101][101];
int dp[101][101][81];
int count = 0;
int width = 0;
int height = 0;
string word;
int dfs(int startx, int starty, int K, int step) {
	int sum = 0;
	if (step == word.length() - 1) {
		dp[starty][startx][step]++;
		return 1;
	}
	int left = startx - K >= 0 ? startx - K : 0;
	int right = startx + K <= width ? startx + K : width;
	int north = starty - K >= 0 ? starty - K : 0;
	int south = starty + K <= height ? starty + K : height;
	for (int x = north; x <= south; x++) {
		if (arr[x][startx] == word[step + 1] && (x!=starty)) {
			if (dp[x][startx][step + 1]) {
				sum += dp[x][startx][step + 1];
			}
			else {
				sum += dfs(startx, x, K, step + 1);
			}
		}
	}
	for (int x = left; x <= right; x++) {
		if (arr[starty][x] == word[step + 1] && (x!=startx)) {
			if (dp[starty][x][step + 1]) {
				sum += dp[starty][x][step + 1];
			}
			else {
				sum += dfs(x, starty, K, step + 1);
			}
		}
	}
	dp[starty][startx][step] += sum;
	return sum;
}
int main() {
	int N, M, K;
	string temp;
	int routesum = 0;
	cin >> N >> M >> K;
	height = N - 1;
	width = M - 1;
	getline(cin, temp);
	for (int x = 0; x < N; x++) {
		getline(cin, temp);
		for (int y = 0; y < M; y++) {
			arr[x][y] = temp[y];
		}
	}
	getline(cin, word);
	for (int x = 0; x < N; x++) {
		for (int y = 0; y < M; y++) {
			if (arr[x][y] == word[0]) {
				routesum += dfs(y, x, K, 0);
			}
		}
	}
	printf("%i", routesum);
}

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

문제

문제

출처

ICPC

시간초과 도와주세요

sj7699 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말