题目链接:回家
第一个点超时,是为什么啊
代码如下:(最后一个点是判重问题也WA了)
#include<iostream>
using namespace std;
int ans=2147483647;
int a[20][20];
int b[20][20];
int n,m;
int sx, sy;
int fx,fy;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void dfs(int i,int j,int step,int blood)
{
if(i==fx&&j==fy)
{
ans=min(ans,step);
return;
}
if(blood==1)return;
for(int k=0;k<4;k++)
{
int ii=i+dx[k];
int jj=j+dy[k];
if(ii<1||ii>n||jj<1||jj>m)continue;
if(b[ii][jj]==0&&a[ii][jj]!=0)
{
if(a[ii][jj]==1||a[ii][jj]==3)
{
b[ii][jj]=1;
dfs(ii,jj,step+1,blood-1);
b[ii][jj]=0;
}
if(a[ii][jj]==4)
{
b[ii][jj]=1;
dfs(ii,jj,step+1,6);
b[ii][jj]=0;
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]==2)
{
sx=i;
sy=j;
}
if(a[i][j]==3)
{
fx=i;
fy=j;
}
}
}
b[sx][sy]=1;
dfs(sx,sy,0,6);
if(ans!=2147483647)cout<<ans<<endl;
else cout<<-1<<endl;
return 0;
}
第一个点的测试数据:
9 9
2 0 1 4 1 1 4 1 1
1 0 4 1 1 4 1 1 1
1 4 1 1 4 1 1 1 4
4 1 1 4 1 4 1 4 1
1 1 4 1 1 1 4 1 1
1 4 1 1 1 4 1 1 1
4 1 4 1 4 1 1 1 1
1 1 1 4 1 1 1 1 1
1 1 4 1 1 1 1 1 3