问题标题: 酷町堂：5014 ：中国象棋

题目描述 Description

酷町喵和她的小伙伴**国际象棋，国际象棋的棋盘大小为8*8，其中有一个棋子叫做国王（King）。国王可以向上下左右以及斜着的共8个方向走一步。现在棋盘上有的位置被敌人占领不能通过。酷町喵想知道，如果要把国王从现在的一个位置移动到某个位置，一共有多少种可能的路径。将这些路径打印出来。

输入描述 Input Description

第一行，四个空格隔开的整数，sx sy ex ey，(sx,sy)表示起点位置，(ex,ey)表示终点位置
接下来8行，每行8个空格隔开的整数，0表示这个位置可以通过，1表示这个位置不能通过

输出描述 Output Description

前五行，每行一个从起点到终点的路径，国王移动的方向是从正上方开始，顺时针转动，不足5种方案则有多少种打印多少种
第六行，一个整数，表示从起点到终点最多的方案数

这道题按照正常深搜代码写会超时， 求助？？

#include<iostream>
#include<sstream>
#include<list>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<iomanip>
using namespace std;
int sx, sy, ex, ey, vis[10][10], g[10][10], d, cnt=1;
struct king{
    int x, y;
}path[100];
int ans, dir[10][2]={{0}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
void dfs(int x, int y, int bs)
{
    path[bs].x=x;
    path[bs].y=y;
    if(x==ex && y==ey)
    {
        ans++;
        if(cnt<=5)
        {
            cnt++;
            for(int i=1; i<bs; i++)
            {
                cout<<'('<<path[i].x<<','<<path[i].y<<')'<<"->";
            }
            cout<<'('<<path[bs].x<<','<<path[bs].y<<')'<<endl;        
        }
    }
    for(int i=1; i<=8; i++)
    {
        int nx=x+dir[i][0], ny=y+dir[i][1];
        if(nx>=1&&nx<=8&&ny>=1&&ny<=8&&!g[nx][ny]&&!vis[nx][ny])
        {
            vis[nx][ny]=1;
            dfs(nx, ny, bs+1);
            vis[nx][ny]=0; 
        }
    }
}
int main()
{
    cin>>sx>>sy>>ex>>ey;
    for(int i=1; i<=8; i++)
    {
        for(int j=1; j<=8; j++)
        {
            cin>>d;
            g[i][j]=d;
        }
    }
    vis[sx][sy]=1;
    dfs(sx, sy, 1);
    cout<<ans;
    return 0;
}