这是一道略复杂的常规BFS题,但我想用DFS来解决,结果写出代码却总是主函数异常返回,不知哪里错了,检查半天也没发现,以后再看看吧。
Code
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
struct stone{int T,X,Y;};
bool cmp(stone S1,stone S2){return S1.T<S2.T;}
int M,b[305][305],m[305][305],Tmin[90005],p,tmin=99999999,obx,oby;
stone S[50005];
void dfs(int t,int no,int x,int y)
{
if(t>Tmin[p]||m[x][y]==0||x>300||y>300||t>90000-M)return;
if(obx==x&&oby==y)
{
Tmin[p]=min(Tmin[p],t);
return;
}
if(no<=M)
{
while(S[no].T<=t)
{
m[S[no].X][S[no].Y]=0;
m[max(0,S[no].X-1)][S[no].Y]=0;
m[S[no].X+1][S[no].Y]=0;
m[S[no].X][S[no].Y+1]=0;
m[S[no].X][max(0,S[no].Y-1)]=0;
no++;
}
}
/*for(int i=0;i<=10;i++)
{
for(int j=0;j<=10;j++)
{
cout<<m[i][j]<<' ';
}
cout<<endl;
}*/
if(x<300&&m[x+1][y]==1)
{
m[x][y]=0;
dfs(t+1,no,x+1,y);
m[x+1][y]=1;
}
if(y<300&&m[x][y+1]==1)
{
m[x][y]=0;
dfs(t+1,no,x,y+1);
m[x][y]=1;
}
if(x>0&&m[x-1][y]==1)
{
m[x][y]=0;
dfs(t+1,no,x-1,y);
m[x][y]=1;
}
if(y>0&&m[x][y-1]==1)
{
m[x][y]=0;
dfs(t+1,no,x,y-1);
m[x][y]=1;
}
return;
}
int main()
{
cin>>M;
for(int i=1;i<=90000-M;i++) Tmin[i]=609;
for(int i=1;i<=M;i++)
{
cin>>S[i].T>>S[i].X>>S[i].Y;
b[S[i].X][S[i].Y]=1;
b[S[i].X+1][S[i].Y]=1;
b[max(0,S[i].X-1)][S[i].Y]=1;
b[S[i].X][max(0,S[i].Y-1)]=1;
b[S[i].X][S[i].Y+1]=1;
}
sort(S+1,S+M+1,cmp);
for(int i=0;i<=300;i++)
for(int j=0;j<=300;j++)
{
if(i==0&&j==0)continue;
if(b[i][j]==0&&i+j<tmin)
{
for(int ii=0;ii<=300;ii++)
for(int jj=0;jj<=300;jj++)
m[ii][jj]=1;
p++;
obx=i;
oby=j;
dfs(0,1,0,0);cout<<2<<endl;
tmin=min(tmin,Tmin[p]);
}
}
if(tmin==99999999)
cout<<-1;
else
cout<<tmin;
return 0;
}
标签:stone,return,int,S1,&&,解决,P2895,include
From: https://www.cnblogs.com/gongkai/p/17522314.html