求助!!!!!
心情好大晚上顺手来写个题结果自闭,a题记忆化写的为什么只能过9成数据。会wa,哪个大佬能大发慈悲帮忙看看代码么。。。看了a了的大佬们的写的直接搜索剪枝,照着撸了一个也是90%。另外是tle了。。感觉吃了奥里给一样。。
#include "cstdio"
#include "cstring"
#include "iostream"
const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};
#define INF 0x7f7f7f
const int maxn = 100+20;
int d[maxn][maxn];
int mz[maxn][maxn];
struct node{
int x,y;
};
node p1,p2;
void dfs(int y,int x,int step,int dir)
{
if(d[y][x]==-1)
d[y][x]=step;
else if(d[y][x]<=step)
return;
else
d[y][x]=step;
if(y==p2.y&&x==p2.x)
return;
for(int i=0;i<4;i++)
{
int nx=dx[i]+x;
int ny=dy[i]+y;
if(mz[ny][nx]==1)
continue;
if(i==dir)
dfs(ny,nx,step,dir);
else dfs(ny,nx,step+1,i);
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<maxn;i++)
for(int j=0;j<maxn;j++)
mz[i][j]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
char c;
std::cin>>c;
if(c!='x')
mz[i][j]=0;
if(c=='A')
p1.x=j,p1.y=i;
if(c=='B')
p2.x=j,p2.y=i;
}
}
memset(d,-1,sizeof(d));
dfs(p1.y,p1.x,0,-1);
printf("%d\n",d[p2.y][p2.x]==-1?d[p2.y][p2.x]:d[p2.y][p2.x]-1);
}
#include "cstring"
#include "iostream"
const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};
#define INF 0x7f7f7f
const int maxn = 100+20;
int d[maxn][maxn];
int mz[maxn][maxn];
struct node{
int x,y;
};
node p1,p2;
void dfs(int y,int x,int step,int dir)
{
if(d[y][x]==-1)
d[y][x]=step;
else if(d[y][x]<=step)
return;
else
d[y][x]=step;
if(y==p2.y&&x==p2.x)
return;
for(int i=0;i<4;i++)
{
int nx=dx[i]+x;
int ny=dy[i]+y;
if(mz[ny][nx]==1)
continue;
if(i==dir)
dfs(ny,nx,step,dir);
else dfs(ny,nx,step+1,i);
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<maxn;i++)
for(int j=0;j<maxn;j++)
mz[i][j]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
char c;
std::cin>>c;
if(c!='x')
mz[i][j]=0;
if(c=='A')
p1.x=j,p1.y=i;
if(c=='B')
p2.x=j,p2.y=i;
}
}
memset(d,-1,sizeof(d));
dfs(p1.y,p1.x,0,-1);
printf("%d\n",d[p2.y][p2.x]==-1?d[p2.y][p2.x]:d[p2.y][p2.x]-1);
}