谁能告告我为什么我的代码不听我的使唤

P1746 离开中山路

④纱 @ 2020-10-06 18:15:32

#include<bits/stdc++.h>
using namespace std;
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
int n,qi,qj,zi,zj,head=0,tail=1,k;
int b[1005][1005],q[1000005][4];
char a[1005][1005];
bool pd(int i1,int jjj){
    if(i1<1 || i1>n)
      return false;
    if(jjj<1 || jjj>n)
      return false;
    if(b[i1][jjj]==1)
      return false;
    if(a[i1][jjj]=='1'){
        cout<<i1<<" "<<jjj<<" "<<endl<<a[i1][jjj]<<endl;
        return false;
    }
    return true;
}
void bfs(int i,int j){
    do{
        head++;
        for(k=1;k<=4;k++){
            int ii=i+dx[k],jj=j+dy[k];
            if(pd(ii,jj)){
                tail++;
                b[ii][jj]=1;
                q[tail][1]=ii;
                q[tail][2]=jj;
                q[tail][3]=q[head][3]+1;
                if(ii==zi && jj==zj)
                  exit(0);
            }
        }
    }while(head<tail);
}
int main()
{
    cin>>n;
    for(int l=1;l<=n;l++)
      scanf("%s",a[l]);
    cin>>qi>>qj>>zi>>zj;
    q[1][1]=qi;
    q[1][2]=qj;
    b[qi][qj]=1;
    bfs(qi,qj);
    cout<<q[tail][3];
    return 0;
}

3
001
101
100
1 1 3 3
1 2
1
1 2
1
1
--------------------------------
Process exited after 11.81 seconds with return value 0
请按任意键继续. . .

a数组：	0	0	1
1	0	1
1	0	0

它认为a[1][2]==1

by ④纱 @ 2020-10-06 18:20:35

希望大家不要写dfs（除非dalao）

我以下的dfs AC*1 TLE*9

#include<bits/stdc++.h>
using namespace std;
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
int n,qi,qj,zi,zj,min1=100000000,s;
int b[1005][1005];
char a[1005][1005];
bool pd(int i1,int j1){
    if(i1<1 || i1>n || j1<1 || j1>n || b[i1][j1]==1 || a[i1][j1]=='1')
      return false;
    return true;
}
void dfs(int i,int j){
    if(i==zi && j==zj){
        if(s<min1)
          min1=s;
    }
    else{
        for(int k=1;k<=4;k++){
            int ii=i+dx[k],jj=j+dy[k];
            if(pd(ii,jj)){
                b[ii][jj]=1;
                s++;
                dfs(ii,jj);
                b[ii][jj]=0;
                s--;
            }
        }
    }
}
int main()
{
    cin>>n;
    for(int l=1;l<=n;l++)
      scanf("%s",a[l]);
    cin>>qi>>qj>>zi>>zj;
    b[qi][qj]=1;
    dfs(qi,qj);
    cout<<min1;
    return 0;
}

by MilkyCoffee @ 2020-10-06 18:27:44

@④纱重构吧

by MilkyCoffee @ 2020-10-06 18:28:12

粗略看了一眼时限，DFS连20%的数据都过不了

by MilkyCoffee @ 2020-10-06 18:28:56

要用bfs

by ④纱 @ 2020-10-06 18:36:13

我的第一个就是bfs 只不过还在调

by konjacq @ 2020-10-06 18:37:44

@牛奶小咖啡实际上DFS+记忆化写得好看大概是能过完的(大概

by konjacq @ 2020-10-06 18:40:22

@④纱您的DFS加个记忆化应该就能过

#include<bits/stdc++.h>
using namespace std;
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
int n,qi,qj,zi,zj,min1=100000000,s;
int b[1005][1005];
char a[1005][1005];
bool pd(int i1,int j1){
    if(i1<1 || i1>n || j1<1 || j1>n || b[i1][j1]==1 || a[i1][j1]=='1')
      return false;
    return true;
}
void dfs(int i,int j){
    if(i==zi && j==zj){
        if(s<min1)
          min1=s;
    }
    else{
        for(int k=1;k<=4;k++){
            int ii=i+dx[k],jj=j+dy[k];
            if(pd(ii,jj)&&b[ii][jj]>b[i][j]+1){
                b[ii][jj]=b[i][j]+1;
                s++;
                dfs(ii,jj);
                s--;
            }
        }
    }
}
int main()
{
    cin>>n;
    for(int l=1;l<=n;l++) {
      scanf("%s",a[l]);
      memset(b,0x3f,sizeof(b));
    }
    cin>>qi>>qj>>zi>>zj;
    b[qi][qj]=1;
    dfs(qi,qj);
    cout<<min1;
    return 0;
}

by Black_Porridge @ 2020-10-06 18:42:53

~~其实SPFA好像也行~~

by ④纱 @ 2020-10-07 09:07:59

谢谢，已AC

#include<bits/stdc++.h>

using namespace std;

int dx[5]={0,0,0,1,-1};

int dy[5]={0,1,-1,0,0};

int n,qi,qj,zi,zj,head=0,tail=1,k;

int b[1005][1005],q[1000005][4];

char a[1005][1005];

bool pd(int i1,int jjj){

    if(i1<1 || i1>n)

      return false;

    if(jjj<1 || jjj>n)

      return false;

    if(b[i1][jjj]==1)

      return false;

    if(a[i1][jjj]=='1')

      return false;

    return true;

}

void bfs(int i,int j){

    do{

        head++;

        for(k=1;k<=4;k++){

            int ii=q[head][1]+dx[k],jj=q[head][2]+dy[k];

            if(pd(ii,jj)){

                tail++;

                b[ii][jj]=1;

                q[tail][1]=ii;

                q[tail][2]=jj;

                q[tail][3]=q[head][3]+1;

                if(ii==zi && jj==zj)

                  return;

            }

        }

    }while(head<tail);

}

int main()

{

    cin>>n;

    for(int l=1;l<=n;l++)

      scanf("%s",a[l]+1);

    cin>>qi>>qj>>zi>>zj;

    q[1][1]=qi;

    q[1][2]=qj;

    b[qi][qj]=1;

    bfs(qi,qj);

    cout<<q[tail][3];

    return 0;

}