寻找最后之作-bfs

题目传送：寻找最后之作

题目描述：
总计230万人，其中学生占80%的学园都市，所有学生必须接受超能力开发。在领土方面，分为23个学区，每个学区有其不同职能。学园都市并无常备武装力量，甚至不存在警察。取而代之的是从学生中挑选出的风纪委员（Judgement）和教师自愿参与的警备员（Anti-Skill）维护治安，甚至可以组织成对外打击军队。其科技高度发达，领先于外域大约20至30年，高度的科学技术不仅使其合作组织遍布世界各地，为了防止外部势力渗透、科学技术流失、学园都市对人口出入进行严格的管制。
在学园都市内，众所周知，有一位白发苍苍，行动不便的老人，由于他只能拄着拐杖慢慢行走，连回头都十分不方便，所以大家都叫他“一方通行”，不过好在一直有一个可爱的小女孩——最后之作（Last Order）陪在他身边，他的晚年生活不再寂寞，而是充满了色彩。
但是有一天，在他们出门散步的时候，“我的肚子饿了，想吃冰淇淋啦！御坂御坂摸着自己的肚子，渴望地盯着你说道”，小女孩就跑掉了，老人非常着急，你能帮他找到正确的道路，尽快追上最后之作吗？

输入描述:
第一行是一个正整数T，代表输入数据的组数。每组数据的第一行有两个正整数，m，n。m为地图的长度，n为地图的宽度（m，n<=100）。接下来的m行中，每行为一个长度为n的字符串，“.”表示可以通行，“#”表示不可以通行，“A”为一方通行所在地，“L”为最后之作所在地。每一步可以有八个方向（上、下、左、右、左上、左下、右上、右下）。

输出描述:
对于每组输入数据，如果最后可以找到最后之作，输出一个整数，为消耗的最小步数，如果无法到达，输出“I Need Move Point”（有空格，没有引号）。

示例1
输入
2
3 3
A##
..#
#.L
1 4
A.#L

输出
2
I Need Move Point

bfs

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+5;
int t,m,n;
char a[maxn][maxn];
int book[maxn][maxn];
int nxt[8][2]={{0,1},{0,-1},{1,0},{-1,0},{-1,-1},{-1,1},{1,-1},{1,1}};
struct note{
    int x;
    int y;
    int s;
};
note q[maxn*maxn];
int main(){
    cin>>t;
    int stx,sty;
    for(int k=0;k<t;k++){
        int tx,ty;
        cin>>m>>n;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                cin>>a[i][j];
                if(a[i][j]=='A')
                    stx=i,sty=j;               
            }
            getchar();//吸收回车
        }
        memset(book,0,sizeof book);
        int head=1,tail=1;
        q[tail].x=stx;
        q[tail].y=sty;
        q[tail].s=0;
        tail++;
        book[stx][sty]=1;
        int flag=0;
        while(head<tail){
            for(int i=0;i<8;i++){
                tx=q[head].x+nxt[i][0];
                ty=q[head].y+nxt[i][1];
                if(tx>=0&&tx<m&&ty>=0&&ty<n&&book[tx][ty]==0&&(a[tx][ty]=='.'||a[tx][ty]=='L')){
                    book[tx][ty] = 1;
                    q[tail].x = tx;
                    q[tail].y = ty;
                    q[tail].s = q[head].s+1;
                    tail++;
                }
                if(a[tx][ty]=='L'){
                    flag=1;
                    break;
                }
            }
            if(flag==1)break;
            head++;
        }
        if(flag==1)
            cout<<q[tail-1].s<<endl;
        else cout<<"I Need Move Point"<<endl;
    }
    return 0;
}

STL实现

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e2+10;
char e[maxn][maxn];
int book[maxn][maxn];
int flag,ans;
int m,n;
int nxt[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
struct point{
    int x,y,s;
    point(int xx,int yy,int ss){//构造函数定义
        x=xx;
        y=yy;
        s=ss;
    }
};
queue<point>q;
void bfs(int sx,int sy){
    memset(book,0,sizeof(book));
    q=queue<point>();//实例化
    q.push(point(sx,sy,0));
    book[sx][sy]=1;
    while(!q.empty()){
        point u=q.front();
        for(int i=0;i<8;i++){
            //point v;//切记初始化
            point v=point(0,0,0);
            v.x=u.x+nxt[i][0];
            v.y=u.y+nxt[i][1];
            v.s=u.s+1;
            if(v.x>=1&&v.x<=m&&v.y>=1&&v.y<=n&&e[v.x][v.y]!='#'&&book[v.x][v.y]==0){
                q.push(v);
                book[v.x][v.y]=1;
                if(e[v.x][v.y]=='L'){
                    flag=1;
                    ans=v.s;
                    break;
                }
            }            
        }
        if(flag==1)break;
        q.pop();
    }
}
int main(){
    int t;
    int sx,sy;
    cin>>t;
    for(int k=1;k<=t;k++){
        flag=0;
        cin>>m>>n;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                cin>>e[i][j];
                if(e[i][j]=='A'){
                    sx=i;
                    sy=j;
                }                    
            }
            getchar();//切记char型的回车问题
        }
        bfs(sx,sy);
        if(flag==1)cout<<ans<<endl;
        else cout<<"I Need Move Point"<<endl;
    }
    return 0;
}

无构造函数写法：

#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
struct node{//记录点的坐标和走的步数
    int x;
    int y;
    int step;
}s;
int m,n;
char a[maxn][maxn];
const int nxt[8][2]={{1,0},{0,-1},{-1,0},{0,1},{-1,1},{-1,-1},{1,1},{1,-1}};
int book[maxn][maxn],sx,sy,ex,ey;//book用来标记这个点是否走过
int bfs(int xx, int yy){
    queue<node>p;
    s.x=xx;
    s.y=yy;
    s.step=0;
    p.push(s);
    while(!p.empty()){//队列为空表示遍历完了
        int nx,ny,nstep;
        nx=p.front().x;
        ny=p.front().y;
        nstep=p.front().step;
        if(nx==ex&&ny==ey)return nstep;//如果到达终点就返回步数退出函数
        p.pop();
        for (int i=0;i<8;i++){
            int tx,ty,tstep;
            tx=nx+nxt[i][0];
            ty=ny+nxt[i][1];
            if(tx<0||ty<0||tx>=m||ty>=n||book[tx][ty]==1||a[tx][ty]=='#') continue;
            book[tx][ty]=1;
            tstep=nstep+1;
            s.x=tx;
            s.y=ty;
            s.step=tstep;
            p.push(s);//把符合条件的点入队
        }
    }
    return -1;//遍历完了还没有退出表示走不到终点，返回-1表示走不到
}
int main(){
    int T;
    cin>>T;
    for(int k= 0;k<T;k++){
        cin >> m >> n;        
        for (int i= 0; i<m; i++){
            for (int j=0;j<n;j++){
                cin>>a[i][j];
                if(a[i][j]=='A'){
                    sx=i;
                    sy=j;
                }
                if(a[i][j]=='L'){
                    ex= i;
                    ey =j;
                }
            }
            getchar();
        }
        memset(book,0,sizeof(book));
        int ans;
        ans=bfs(sx,sy);
        if(ans >= 0)
            printf("%d\n",ans);
        if(ans==-1)
            printf("I Need Move Point\n");
    }
    return 0;
}

dfs超时

//dfs超时
#include<bits/stdc++.h>
using namespace std;
const int maxn=100+5;
int book[maxn][maxn];
char a[maxn][maxn];
int m,n,t,ans;
int stx,sty;
int nxt[8][2]={{0,1},{0,-1},{1,0},{-1,0},{-1,-1},{-1,1},{1,-1},{1,1}};
void dfs(int tx,int ty,int step){ 
    if(a[tx][ty]=='L'){
        ans=min(ans,step);
    }    
    int x,y;
    for(int i=0;i<8;i++){
        x=tx+nxt[i][0];
        y=ty+nxt[i][1];
        if(x>=0&&x<m&&y>=0&&y<n&&book[x][y]==0&&(a[x][y]=='.'||a[x][y]=='L')){
            book[x][y]=1;
            dfs(x,y,step+1);
            book[x][y]=0;
        }        
    }
}
int main(){
    cin>>t;
    for(int k=1;k<=t;k++){
        cin>>m>>n;
        ans=1e9;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                cin>>a[i][j];
                if(a[i][j]=='A'){
                    stx=i;
                    sty=j;
                }
            } 
        }
        book[stx][sty]=1;
        dfs(stx,sty,0);
        book[stx][sty]=0;
        if(ans==1e9)   cout<<"I Need Move Point"<<endl;
        else cout<<ans<<endl;
    }                 
    return 0;
}