[TIOJ] 1196. 小豬Piggy

題目連結:http://tioj.infor.org/problems/1196

---

雖然本題理應是要DP，但其實n小小的(才10而已)，直接BFS甚至DFS就好了XD

#include <stdio.h>

int size, maze[11][11];

int DFS(int x, int y, int val){
	if(maze[x][y] == 22)
		return val;
	else if(maze[x][y] == -1)
		return -1;
	else{
		if(x<size-1 && y<size-1){
			int a = DFS(x+1, y, val + maze[x][y]);
			int b = DFS(x, y+1, val + maze[x][y]);
			return (a>b)?a:b;
		}else if(x < size-1)
			return DFS(x+1, y, val+maze[x][y]);
		else
			return DFS(x, y+1, val+maze[x][y]);
	}
}

int main(){
	scanf("%d\n",&size);
	for(int i=0;i<size;i++){
		for(int j=0;j<size;j++){
			char c=getchar();
			maze[i][j] = (c=='A') ? 71 : (c=='B') ? 22 : (c=='X') ? -1 : c-'0';
		}
		getchar();
	}
	int ans=DFS(0,0,-71);
	if(ans == -1)
		puts("X");
	else
		printf("%d",ans);
	return 0;
}