70pts求助dalao

P1746 离开中山路

M_WC1S_M0 @ 2022-06-01 17:55:46

原来是80分,错#3,#8,现在改了一个

if(t.x<=0||t.y<=0||t.x>n||t.y>n||g[t.x][t.y]=='1'||dp[t.x][t.y]<=dp[p.x][p.y]+1)

里面的‘’,应该是对的,但只有70pts了

代码:

#include<queue>
#include<cstdio>
#include<iostream>
using namespace std;
int n;
char g[1005][1005];
int s[2],e[2];
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int dp[1005][1005];
struct node
{
    int x,y;
}p,t;
queue<node> q;
int main()
{
    for(int i=0;i<1005;i++)
        for(int j=0;j<1005;j++)
            dp[i][j]=1<<30;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>g[i][j];
    scanf("%d%d%d%d",&s[0],&s[1],&e[0],&e[1]);
    p.x=s[0];
    p.y=s[1];
    dp[s[0]][s[1]]=0;
    q.push(p);
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        if(p.x==e[0]&&p.y==e[1])
            break;
        for(int i=0;i<4;i++)
        {
            t.x=p.x+dir[i][0];
            t.y=p.y+dir[i][1];
            if(t.x<=0||t.y<=0||t.x>n||t.y>n||g[t.x][t.y]=='1'||dp[t.x][t.y]<=dp[p.x][p.y]+1)
                continue;
            dp[t.x][t.y]=dp[p.x][p.y]+1;
            q.push(t);
        }
    }
    printf("%d",dp[e[0]][e[1]]);
    return 0;
} 

by Qiancy1427 @ 2022-06-01 18:05:26

@FAN_1106 是超时了吗?如果是,建议判断一下当前点是否为终点,然后跳出(写成函数可能更好实现)


by M_WC1S_M0 @ 2022-06-01 18:07:18

@Qiancy1427 这个写了,不是超时


by Qiancy1427 @ 2022-06-01 18:11:20

@FAN_1106 哦我看了一下我之前的AC代码发现了,这题很坑

if(sx==fx&&sy==fy){
    cout<<0;
    return 0;
}

加上这个才行,就是说它起点和终点可能重合


by Qiancy1427 @ 2022-06-01 18:11:41

我之前就因为这个卡了好久


|