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：

30011011001 1 3 3

输出样例#1：

4

说明

20%数据：n<=100

100%数据：n<=1000

 

#include
      
       #include
       
        #include
        
         #include
         
          #define N 1200using namespace std;char ch;bool vis[N][N];int n,sx,sy,ex,ey,ans;int xx[4]={
    0,0,1,-1},yy[4]={
    1,-1,0,0};int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9') ch=getchar();    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}    return x*f;}void dfs(int x,int y,int s){    if(x==ex&&y==ey)    {        ans=min(ans,s);        return ;    }    if(x<1||y<1||x>n||y>n||vis[x][y]) return ;    vis[x][y]=true;++s;    for(int i=0;i<4;i++)    {        int fx=x+xx[i],fy=y+yy[i];        dfs(fx,fy,s);    }    vis[x][y]=false;}int main(){    n=read();    for(int i=1;i<=n;i++)     for(int j=1;j<=n;j++)     {         cin>>ch;         if(ch=='1') vis[i][j]=true;      }     sx=read(),sy=read(),ex=read(),ey=read();    ans=0x3f3f3f3f;dfs(sx,sy,0);    printf("%d",ans);    return 0;}
         
        
       
      

迷宫问题最好使用bfs，因为dfs可能会T的很惨、、

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 2200using namespace std;char ch;bool vis[N][N];int xx[4]={
   0,0,1,-1},yy[4]={
   1,-1,0,0};int n,sx,sy,ex,ey,ans,tail,head,q[N*N][3],d[N][N];int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9') ch=getchar();    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}    return x*f;}int main(){    n=read();    for(int i=1;i<=n;i++)     for(int j=1;j<=n;j++)     {         cin>>ch;         if(ch=='1') vis[i][j]=true;      }     sx=read(),sy=read(),ex=read(),ey=read();    memset(d,0x3f3f3f3f,sizeof(d));d[sx][sy]=0;    q[tail][1]=sx,q[tail][2]=sy,++tail;    while(head
          
           n||fy>n) continue; if(d[fx][fy]>(d[x][y]+1)) d[fx][fy]=d[x][y]+1,q[tail][1]=fx,q[tail][2]=fy,++tail; } }}