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
我之前就因为这个卡了好久