P1746 离开中山路

题目背景

《爱与愁的故事第三弹·shopping》最终章。

题目描述

爱与愁大神买完东西后，打算坐车离开中山路。现在爱与愁大神在x1,y1处，车站在x2,y2处。现在给出一个n×n（n<=1000）的地图，0表示马路，1表示店铺（不能从店铺穿过），爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间，他要求最短到达目的地距离（a[i][j]距离为1）。你能帮他解决吗？

输入输出格式

输入格式：

第1行：一个数 n

第2行~第n+1行：整个地图描述（0表示马路，1表示店铺，注意两个数之间没有空格）

第n+2行：四个数 x1,y1,x2,y2

输出格式：

只有1行：最短到达目的地距离

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

20%数据：n<=100

100%数据：n<=1000

思路：bfs。dfs和spfa等图论算法都会gg。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,ans=0x7f7f7f7f;

int sx,sy,tx,ty;

int map[][];

int dx[]={,,,-};

int dy[]={-,,,};

void dfs(int x,int y,int tot){

    if(tot>=ans)    return ;

    if(x==tx&&y==ty){

        ans=min(ans,tot);

        return ;

    }

    for(int i=;i<;i++){

        int cx=x+dx[i];

        int cy=y+dy[i];

        if(!map[cx][cy]&&cx>=&&cx<=n&&cy>=&&cy<=n){

            map[cx][cy]=;

            dfs(cx,cy,tot+);

            map[cx][cy]=;

        }

    }

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++){

            char x;cin>>x;

            map[i][j]=x-'';

        }

    scanf("%d%d%d%d",&sx,&sy,&tx,&ty);

    dfs(sx,sy,);

    cout<<ans;

}

TLE的dfs

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,ans=0x7f7f7f7f;

int sx,sy,tx,ty;

int map[][];

int dx[]={,,,-};

int dy[]={-,,,};

struct nond{

    int x,y,step;

};

queue<nond>que;

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++){

            char x;cin>>x;

            map[i][j]=x-'';

        }

    scanf("%d%d%d%d",&sx,&sy,&tx,&ty);

    nond tmp;tmp.x=sx;tmp.y=sy;tmp.step=;

    que.push(tmp);map[sx][sy]=;

    while(!que.empty()){

        nond now=que.front();

        que.pop();

        for(int i=;i<;i++){

            nond c;c.x=now.x+dx[i];

            c.y=now.y+dy[i];

            c.step=now.step+;

            if(c.x==tx&&c.y==ty){ cout<<c.step;return ; }

            if(c.x>=&&c.x<=n&&c.y>=&&c.y<=n&&!map[c.x][c.y]){

                map[c.x][c.y]=;

                que.push(c);

            }

        }

    }

}

巴特西

洛谷 P1746 离开中山路

P1746 离开中山路

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章