首页 > 代码库 > 【搜索】【the first editoral】OpenJudge 我是最快的马

【搜索】【the first editoral】OpenJudge 我是最快的马

2024-07-14 01:21:18   215人阅读

【题面】【我们都知道，在中国象棋中，马是走日字步的。现给定马的起始坐标与终点坐标，求出马最快能到达的路线。如果有多条路线都是步数最少的，则输出路线的数目。
注意，此时棋盘上可能会有一些其它的棋子，这些棋子是会憋马脚的，注意！】

BFS好题。确实是好题。我出错的地方有几个：1、把蹩马脚的点和访问过的点混淆，应该分别标记；2、访问终点后将终点标记，而这题显然不能；3、标记路线的时候出了小差错。大概就这些。

#include<cstdio>#include<queue>#include<stack>#include<iostream>using namespace std;int G[18][18];int dx[]= {-2,-2,2,2,-1,1,-1,1};int dy[]= {-1,1,-1,1,-2,-2,2,2};int method=0;struct Point{    int x,y;    int fa;    int self;    Point(){}    Point(int _x,int _y,int _fa,int _self):x(_x),y(_y),fa(_fa),self(_self){}    bool operator==(Point &tp)    {        if(tp.x==x&&tp.y==y)            return true;        return false;    }}P[150];int cnt=0;int bfs(Point start,Point &endz){    queue<Point> q;    q.push(start);    G[start.x][start.y]=1;    int step=0;    while(!q.empty())    {        step++;        int size=q.size();        while(size--)        {            Point now=q.front();//            cout<<now.x<<" "<<now.y<<" "<<now.fa<<" "<<now.self<<endl;            q.pop();            for(int i=0; i<8; i++)            {                int nx=now.x+dx[i];                int ny=now.y+dy[i];                int mx=now.x+dx[i]/2;                int my=now.y+dy[i]/2;                                                        //  the point visited was flag and be seeing as the the 蹩马脚！！                if(nx>=0&&nx<=10&&ny>=0&&ny<=10&&G[mx][my]!=2&&!G[nx][ny])                {//                    cout<<nx<<" "<<ny<<endl;                    G[nx][ny]=1;//the cnt is starting from 2,but the P[2] is empty.                    P[cnt]=Point(nx,ny,now.self,cnt);                    cnt++;                    if(P[cnt-1]==endz)                    {                        G[nx][ny]=0;                        endz.fa=P[cnt-1].fa;                        method++;                    }                    else q.push(P[cnt-1]);                }            }        }        if(method>0) return step;    }}int main(){    freopen("a.txt","r",stdin);    int x,y;    scanf("%d%d",&x,&y);    P[cnt++]=Point(x,y,0,0);    scanf("%d%d",&x,&y);    P[cnt++]=Point(x,y,-1,1);    int M;    scanf("%d",&M);    for(int i=0; i<M; i++)    {        scanf("%d%d",&x,&y);        G[x][y]=2;    }    if(P[0]==P[1])        {printf("0\n");return 0;}    int step=bfs(P[0],P[1]);    stack<Point> st;    st.push(P[1]);    int tot=P[1].fa;    while(1)    {        st.push(P[tot]);//        cout<<P[tot].x<<" "<<P[tot].y<<" "<<P[tot].fa<<endl;        if(P[tot]==P[0]) break;        tot=P[tot].fa;    }    if(method==1)    {        while(!st.empty())        {            printf("(%d,%d)",st.top().x,st.top().y);            st.pop();            if(st.size()!=0)                printf("-");        }        printf("\n");    }    else    {        printf("%d\n",step);    }}

 


联系
我们