大学生プログラム設計招待試合(華東師範大学)C:カンガルーのお母さんは子供を探します

カンガルーのお母さんは子供を探しています
Time limit per test: 1.5 seconds
Time limit all tests: 10.0 seconds
Memory limit: 256 megabytes
カンガルーのお母さんは彼女の子供を見つけられなかった.彼女の子供は怪獣に捕まった.
カンガルーのお母さんは今地図の左上にいて、彼女の子供は地図のx行のy列の位置にいます.怪獣はカンガルーのお母さんとゲームをしたいと思っています.彼はカンガルーのお母さんに早く子供を見つけさせたくないです.カンガルーのお母さんは毎秒上下左右の4つの方向に1格(壁のブロックがなければ)を跳ぶことができて、怪獣はいくつかの格子の中で壁を作って、それによって1つの迷路を完成して、カンガルーのお母さんが彼女の子供を見つけることができて、しかし最も速くk秒より小さくてはいけません.
このような迷路を設計してください.
Input
1行目の2つの整数n,m(1≦n,m≦8)は、地図の総行数と総列数を表す.
2行目の3つの整数x,y,k(1≦x≦n,1≦y≦m,x+y>1).
Output
地図を出力します.ちょうどn行m列です..で空き地を表し、*で壁を表す.カンガルーの母親の位置と子供の位置は.で表されている.
データは解を保証する.
Examples
input

2 6
1 3 4

output

.*.***
......

本当に勝手に探してみましたが、書きにくいです.
むやみに跳んで、一歩跳ぶたびに、他の方向に壁を作って、k歩に跳んで終わります
http://acm.ecnu.edu.cn/problem/3260/

#include
#include
#include
using namespace std;
int ok, pk, ex, ey, dir[4][2] = {0,-1,1,0,-1,0,0,1};
char str[15][15];
typedef struct Res
{
	int x, y;
}Res;
Res s[5];
int n, m;
void Sech(int x, int y, int step, int lx, int ly)
{
	int dx, dy, i, x1, y1, x2, y2, x3, y3, k = 0;
	for(i=0;i<=3;i++)
	{
		dx = x+dir[i][0];
		dy = y+dir[i][1];
		if(dx<1 || dx>n || dy<1 || dy>m || dx==lx && dy==ly || str[dx][dy]=='*')
			continue;
		if(dx==ex && dy==ey)
		{
			if(step+1>=pk)
				ok = 1;
			return;
		}
		s[++k].x = dx, s[k].y = dy;
	}
	if(k==3)
	{
		x1 = s[1].x, y1 = s[1].y;
		x2 = s[2].x, y2 = s[2].y;
		x3 = s[3].x, y3 = s[3].y;
		str[x1][y1] = str[x3][y3] = '*';
		Sech(x2, y2, step+1, x, y);
		if(ok)  return;
		str[x1][y1] = '.';
		str[x2][y2] = '*';
		Sech(x1, y1, step+1, x, y);
		if(ok)  return;
		str[x3][y3] = '.';
		str[x1][y1] = '*';
		Sech(x3, y3, step+1, x, y);
		if(ok)  return;
		str[x2][y2] = str[x1][y1] = '.';
	}
	else if(k==2)
	{
		x1 = s[1].x, y1 = s[1].y;
		x2 = s[2].x, y2 = s[2].y;
		str[x1][y1] = '*';
		Sech(x2, y2, step+1, x, y);
		if(ok)  return;
		str[x1][y1] = '.';
		str[x2][y2] = '*';
		Sech(x1, y1, step+1, x, y);
		if(ok)  return;
		str[x2][y2] = '.';
	}
	else if(k==1)
		Sech(s[1].x, s[1].y, step+1, x, y);
}
int main(void)
{
	int i, j;
	scanf("%d%d", &n, &m);
	memset(str, '.', sizeof(str));
	scanf("%d%d%d", &ex, &ey, &pk);
	Sech(1, 1, 0, 0, 0);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
			printf("%c", str[i][j]);
		printf("
");
	}
	return 0;
}