【一本通1330】最少步数

qqwqq

最少步数【传送门】

算法的话,bfs(虽然我到现在也没搞明白

然后嘛,不知道该讲什么qwq:

【一本通1330】最少步数

一只马可以走到的位置qwq

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
using namespace std;
int x3,y3,x2,y2;
int dx[13]={0,-2,-2,-2,-2,-1,-1,1, 1,2,2, 2, 2};//某只马走田或者走日可能移动的位置(横方向上) 
int dy[13]={0, 2, 1,-1,-2, 2,-2,2,-2,2,1,-1,-2};//某只马走田或者走日可能移动的位置(纵方向上)
                                  //dx与dy是已经一一对应的qwq 
int s[101][101];//用来判断这个位置算没算到过&有没有出界&存储步数的神奇多用数组qwq 
int k[10000][4];//队列,用来存储x(k[i][1])和y(k[i][2])和走到这一步时的步数(k[i][3]
int main(){
    scanf("%d%d",&x3,&y3);//读入qwq 
    scanf("%d%d",&x2,&y2);
    memset(s,-1,sizeof(s));//把s数组全部赋值为-1,这样判断不为-1可能出界,没算到的就<0 
    s[1][1]=0;k[1][1]=1;k[1][2]=1;k[1][3]=0;//先把(1,1)入队 
    int h=1,t=1,x,y;//定义队列头尾及x,y 
    while(h<=t){//队列不为空的时候 
        for(int i=1;i<=12;i++){//楼上12种可能的位置一一计算 
            x=k[h][1]+dx[i];
            y=k[h][2]+dy[i];//把它算出来 
            if(x>0&&y>0){//显然如果x,y为负它就出界了 
                if(s[x][y]==-1){/*判断这个位置之前有没有被算过,如果之前被算过了的话,那么显然
                之前到达这个位置的步数小qwq,所以只算第一次到达*/ 
                    s[x][y]=k[h][3]+1; //如果第一次走到,在上个位置的基础上+1 
                    t++;//入队了,尾+1 
                    k[t][1]=x;//分别入队 
                    k[t][2]=y;
                    k[t][3]=s[x][y];
                    if(s[x3][y3]>0&&s[x2][y2]>0)//如果A点和B点都已经走过了,输出这两个点的位置,跑~~ 
                    {
                        cout<<s[x3][y3]<<endl;
                        cout<<s[x2][y2]<<endl;
                        return 0;
                    }
                }
            }
        }
        h++;//否则再计算下一个点的步数(相当于第一个没有搜到答案,就不要它了qwq好哀伤) 
    }
} 

//注释多的吓人qwq

end-

 

上一篇:MAS6012 Project


下一篇:带默认形参值的函数 C++练习