题解 P1747【好奇怪的游戏】

whiteqwq · 2018-08-09 17:08:04 · 题解

看着下面的题解都是bfs的，dfs来一发。

思路：直接搜，如果比之前这个点的步数少就替换。

搜索时使用方向矢量，节省了代码长度。

（注：（各种变量名字含义）

a, b, c, d -> 两匹马的坐标

f[i][j] -> 到达第i行j列需要的步数+1（f[1][1]为1）

dx[],dy[] -> 方向矢量）

#include<bits/stdc++.h>//万能头
using namespace std;
int a,b,c,d,f[25][25],dx[13]={0,2,2,2,2,1,1,-1,-1,-2,-2,-2,-2},dy[13]={0,2,1,-1,-2,2,-2,2,-2,2,1,-1,-2};//前面已经说过了，不解释（貌似已经解释了QWQ）
void dfs(int x,int y,int s){//到达第x行y列，步数为x
    f[x][y]=s;//标记
    for(int u=1;u<=12;u++){//开始拓展
        int ux=x+dx[u],uy=y+dy[u];//找到坐标
        if(ux<1||ux>20||uy<1||uy>20)//判边界
            continue;
        if(f[ux][uy]==0||f[ux][uy]>s+1)//可以拓展
            dfs(ux,uy,s+1);//拓展
    }
}
int main()
{   scanf("%d%d%d%d",&a,&b,&c,&d);
    dfs(a,b,1);
    printf("%d\n",f[1][1]-1);
    memset(f,0,sizeof(f));//别忘清0
    dfs(c,d,1);
    printf("%d\n",f[1][1]-1);
    return 0;
}