POJ 1915 Knight Moves(DFS/BFS)

POJ 1915 Knight Moves(DFS/BFS)

http://poj.org/problem?id=1915

题意:一个N*N的棋牌上,问你中国象棋的马从一个指定点走到另外一个指定点最少需要多少步.

分析:

由下面DFS和BFS的做法可以看出,BFS的代码虽然比DFS的代码复杂,但是对于某些题目速度上还是很有优势的.

本题类似

http://blog.csdn.net/u013480600/article/details/25426851

本题用BFS做法没什么好说的,很容易就可以解决.下面用DFS来做.

用DFS要考虑的情况有:

ans与当前行走距离len大小比较: 剪枝

当前r和c不能越界: 越界判断

当前r和c是否已经到了终点: 终点判断

当前len与dist[r][c]的大小比较: 剪枝

接下来就是递推dfs 8个方向的延伸子节点了.(就算子节点已经走过了,也要延伸)

超时代码: 用DFS做的超时,但是结果应该是对的.程序中为了不用每次初始化vis数组,我做了个小优化,用kase标记vis.可以看源代码.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=300+5;
int dr[]={1,1,-1,-1,2,2,-2,-2};//马能走的8个方向对应的r和c的增量
int dc[]={2,-2,2,-2,1,-1,1,-1};
int vis[maxn][maxn],dist[maxn][maxn];
int ans;
int kase=0;
int R,C;
int sr,sc,er,ec;//起点,终点
void dfs(int r,int c,int len)//表示从起点走到(r,c)格,当前需要len步
{
    if(r<0||r>=R||c<0||c>=C||len>=ans) return;  //越界判断+剪枝
    if(r==er&&c==ec) {ans=min(ans,len); return;} //剪枝
    if(vis[r][c]==kase && dist[r][c]<=len)         //剪枝
        return ;
    vis[r][c]=kase;//令vis=kase,避免每次都初始化vis数组,节约时间
    dist[r][c]=len;
    for(int d=0;d<8;d++)
    {
        int nr=r+dr[d];
        int nc=c+dc[d];
        dfs(nr,nc,len+1);
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        kase++;
        scanf("%d",&R);
        C=R;
        scanf("%d%d",&sr,&sc);
        scanf("%d%d",&er,&ec);
        ans=R*R;//max(R*R/400,10);//此处可以优化,但是不好优化,不是超时就是WA
        dfs(sr,sc,0);
        printf("%d\n",ans);
    }
    return 0;
}

下面用BFS来做吧.

AC代码:96ms

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=300+5;
int dr[]={1,1,-1,-1,2,2,-2,-2};//马能走的8个方向对应的r和c的增量
int dc[]={2,-2,2,-2,1,-1,1,-1};
int vis[maxn][maxn],dist[maxn][maxn];
int kase=0;
int R,C;
int sr,sc,er,ec;//起点,终点
struct Node
{
    int r,c;
    Node(int r,int c):r(r),c(c){}
};
queue<Node> Q;
int BFS()
{
    while(!Q.empty()) Q.pop();
    if(sr==er && sc==ec) return 0;
    dist[sr][sc]=0;
    vis[sr][sc]=kase;
    Q.push(Node(sr,sc));
    while(!Q.empty())
    {
        Node node=Q.front();Q.pop();
        int r=node.r,c=node.c;
        for(int d=0;d<8;d++)
        {
            int nr=r+dr[d];
            int nc=c+dc[d];
            if(nr>=0&&nr<R&&nc>=0&&nc<C&&vis[nr][nc]!=kase)
            {
                if(nr==er && nc==ec) return dist[r][c]+1;
                dist[nr][nc]=dist[r][c]+1;
                vis[nr][nc]=kase;
                Q.push(Node(nr,nc));
            }
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        //memset(vis,0,sizeof(vis)); //用了kase赋值vis,所以每次都不用初始化vis了
        kase++;
        scanf("%d",&R);
        C=R;
        scanf("%d%d",&sr,&sc);
        scanf("%d%d",&er,&ec);
        printf("%d\n",BFS());
    }
    return 0;
}