UVA 439 Knight Moves --DFS or BFS

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 9

int vis[N][N];
int res;
int dx[8] = {1,1,-1,-1,2,2,-2,-2};
int dy[8] = {2,-2,2,-2,1,-1,1,-1};

inline bool OK(int nx,int ny)
{
    if(nx >= 1 && nx <=8 && ny >= 1 && ny <= 8 && !vis[nx][ny])
        return true;
    return false;
}

void dfs(int sx,int sy,int tx,int ty,int cnt)
{
    if(cnt >= res)
        return;
    if(sx == tx && sy == ty && cnt < res)
    {
        res = cnt;
        return;
    }
    for(int i=0;i<8;i++)
    {
        int nx = sx + dx[i];
        int ny = sy + dy[i];
        if(!OK(nx,ny))
            continue;
        vis[nx][ny] = 1;
        dfs(nx,ny,tx,ty,cnt+1);
        vis[nx][ny] = 0;
    }
    return;
}

int main()
{
    char s1[4],s2[4];
    int sx,sy,tx,ty;
    while(scanf("%s%s",s1,s2)!=EOF)
    {
        sx = s1[0] - ‘a‘ + 1;
        tx = s2[0] - ‘a‘ + 1;
        sy = s1[1] - ‘0‘;
        ty = s2[1] - ‘0‘;
        memset(vis,0,sizeof(vis));
        vis[sx][sy] = 1;
        res = 6;   //·dfs边界，能取到正确的最小值最好，这里设为6或以上即可
        dfs(sx,sy,tx,ty,0);
        printf("To get from %s to %s takes %d knight moves.\n",s1,s2,res);
    }
    return 0;
}