PKU3271 Lilypad Pond

ついに解けました。
解法はBFS+DP。何となくJOI 2011のOrienteeringを彷彿とさせる面倒な問題です。
ちなみにBFSの「1回みたところはもうみない」を忘れてREとTLE量産していて初心者すぎた。

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int c[35][35];
pair<int,int> to[35][35][1000];
int size[35][35];
int dx[]={2,2,1,1,-1,-1,-2,-2};
int dy[]={1,-1,2,-2,2,-2,1,-1};
long long dp[1000][35][35];
int used[35][35];
int bfs[35][35];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)
		for(int j=0;j<b;j++)
			scanf("%d",&c[i][j]);
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			if(c[i][j]==0||c[i][j]==3){
				queue<pair<int,int> >Q;
				Q.push(make_pair(i,j));
				for(int k=0;k<a;k++)
					for(int l=0;l<b;l++)
						bfs[k][l]=0;
				bfs[i][j]=1;
				while(Q.size()){
					int row=Q.front().first;
					int col=Q.front().second;
					Q.pop();
					for(int k=0;k<8;k++){
						if(0<=row+dx[k]&&row+dx[k]<a&&0<=col+dy[k]&&col+dy[k]<b){
							if(c[row+dx[k]][col+dy[k]]==1&&bfs[row+dx[k]][col+dy[k]]==0){
								bfs[row+dx[k]][col+dy[k]]=1;
								Q.push(make_pair(row+dx[k],col+dy[k]));
							}else if(c[row+dx[k]][col+dy[k]]!=2&&bfs[row+dx[k]][col+dy[k]]==0){
								bfs[row+dx[k]][col+dy[k]]=1;
								to[i][j][size[i][j]++]=make_pair(row+dx[k],col+dy[k]);
							}
						}
					}
				}
			}
			if(c[i][j]==3){
				for(int k=0;k<size[i][j];k++)dp[0][to[i][j][k].first][to[i][j][k].second]=1;
			}
		}
	}
	int gx=0;
	int gy=0;
	for(int i=0;i<a;i++)
		for(int j=0;j<b;j++)
			if(c[i][j]==4){
				gx=i;gy=j;
			}
	for(int i=0;i<a*b;i++){
		for(int j=0;j<a;j++){
			for(int k=0;k<b;k++){
				if(used[j][k])continue;
				if(dp[i][j][k]){
					used[j][k]=1;
					for(int l=0;l<size[j][k];l++)dp[i+1][to[j][k][l].first][to[j][k][l].second]+=dp[i][j][k];
				}
			}
		}
		if(used[gx][gy])break;
	}
	bool ok=false;
	for(int k=0;k<a*b;k++){
		if(dp[k][gx][gy]){
			printf("%d\n%lld\n",k,dp[k][gx][gy]);
			ok=true;
			break;
		}
	}
	if(!ok)printf("-1\n");
}