글 읽기 - 경로찾기 질문

HJY 8년 전 0

경로 찾기 어느부분이 잘못된건지 잘모르겠습니다...

점화식이 잘못된거같은데 조언좀 주시면 감사하겠습니다ㅜㅜ.

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<limits.h>
using namespace std;
#define MOD 1000007
int N, M, K;
int cache[55][55][55][55];
int data[55][55];
int max(int a, int b){ if (a < b)return b; else return a; }
int go(int last_visit, int visit_cnt , int y, int x){

	if (visit_cnt < 0) return 0;
	int &ret = cache[last_visit][visit_cnt][y][x];

	if (ret != -1)return ret;

	if (y == N && x == M && visit_cnt == 0)
		return 1;
	ret = 0;	


	if (x + 1 <= M && data[y][x + 1] == 0){
		
		int next_visit = last_visit;
		ret += go(next_visit, visit_cnt, y, x + 1);
		ret %= MOD;

	}
	else if(visit_cnt-1 >=0 && x+1 <= M && data[y][x+1] != 0 && last_visit < data[y][x+1]){
	
		int next_visit = data[y][x + 1];
		ret += go(next_visit, visit_cnt - 1, y, x + 1);
		ret %= MOD;
	}
	if (y+1 <=N && data[y + 1][x] == 0){
		int next_visit = last_visit;
		ret += go(next_visit, visit_cnt, y + 1, x);
		ret %= MOD;
	}
	else if (visit_cnt - 1 >= 0 && y + 1 <= N && data[y + 1][x] != 0 && last_visit < data[y+1][x]){
		int next_visit = last_visit;
		ret += go(next_visit, visit_cnt-1, y + 1, x);
		ret %= MOD;
	}
	
	return ret;
}
int main(){

	//freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	scanf("%d %d %d", &N, &M, &K);
	for (int k = 1; k <= K; k++){
		int y, x;
		scanf("%d %d", &y, &x);
		data[y][x] = k;
	}
	int ans = 0;
	
	for (int k = 0; k <= K; k++){
		memset(cache, -1, sizeof(cache));
		if (data[1][1] != 0)
			ans = go(data[1][1], k-1, 1, 1);
		else
			ans = go(0, k, 1, 1);
		printf("%d ", ans%MOD);
	}


	return 0;
}

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

문제

문제

출처

ICPC

경로찾기 질문

HJY 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말