国际象棋中马走“日”，现请编程输出马从入口跳到出口的一条路径。棋盘上有些点是不能落脚的。如图A中值为1的点不能落脚，值为0的点可落脚。
马在格子中，有8个方向可以探索。探索顺序按图B中的序号顺序进行。
第一行两个整数m,n 表示棋盘有m行n列（m＜＝１０,n＜＝１０） 下面m行每行n个数，全是0或1 ，1表示不能落脚。
6 6
0 1 1 1 1 1
1 1 1 0 1 1
1 0 1 1 1 0
1 1 1 0 0 1
1 1 0 1 1 1
1 1 1 1 0 0
(1,1)-(3,2)-(5,3)-(6,5)-(4,4)-(3,6)-(2,4)-(4,5)-(6,6)
(1,1)-(3,2)-(5,3)-(4,5)-(6,6)
(1,1)-(3,2)-(4,4)-(6,5)-(5,3)-(4,5)-(6,6)
(1,1)-(3,2)-(4,4)-(3,6)-(2,4)-(4,5)-(6,6)
(1,1)-(3,2)-(2,4)-(4,5)-(6,6)
(1,1)-(3,2)-(2,4)-(3,6)-(4,4)-(6,5)-(5,3)-(4,5)-(6,6)
注意： 当不止一条路径时，马选择探索方向的顺序直接影响着输出的路径。 本题规定了马探索方向的顺序。
code
#include<iostream>
using namespace std;
const int dx[8]=
{2,1,-1,-2,-2,-1, 1, 2};
const int dy[8]={1,2, 2, 1,-1,-2,-2,-1};
struct node
{
int x,y;
};
int m,n,map[15][15];
bool visited[15][15]={0},found(false);
node s[120]; int t(0);
//ifstream cin("p1167.in");
// ofstream cout("p1167.out");
void search(int x0,int y0)
{
node p;
if (x0==m&&y0==n)
{
cout<<'('<<s[0].x<<','<<s[0].y<<')';
for (int i=1;i<t;i++)
cout<<"-("<<s[i].x<<','<<s[i].y<<')';
cout<<endl;
return ;
}
for (int i=0;i<8;i++)
{
p.x=x0+dx[i];
p.y=y0+dy[i];
if (p.x<=0||p.x>m||p.y<=0||p.y>n) continue;
if (visited[p.x][p.y]||map[p.x][p.y]==1) continue;
s[t++]=p;
visited[p.x][p.y]=true;
search(p.x,p.y);
--t;
visited[p.x][p.y]=false;
}
}
int main()
{
int i,j;
cin>>m>>n;
for (j=0;j<=n+1;j++)
map[0][j]=map[n+1][j]=1;
for (i=0;i<=n+1;i++)
map[i][0]=map[i][n+1]=1;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
cin>>map[i][j];
s[0].x=s[0].y=1; t=1; visited[1][1]=true;
search(1,1);
return 0;
}