呐,给那些ssd看看,这才是挺好的求助帖
by impuk @ 2020-05-23 20:05:48
如果大家不愿意点开网址,代码就在这里看吧
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,m,c1,c2,d,startx,starty,endx,endy,anss=122510,ansc1=15,ansc2=15;
int a[355][355],p[355][355],book[355][355];
struct node
{
int x;
int y;
int s;
int r1;
int r2;
}Q[122510],temp;
inline int read()
{
int x=0;
char ch=getchar();
while((ch<'0' || ch>'9') && ch!='S' && ch!='T' && ch!='.') ch=getchar();
if(ch=='S') return -1;
if(ch=='T') return -2;
if(ch=='.') return 0;
while(ch>='0' && ch<='9') x=(x<<1+x<<3)+ch^'0',ch=getchar();
return x;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>c1>>c2>>d;
int dx[8]={0,1,0,-1,1,-1,1,-1};
int dy[8]={1,0,-1,0,-1,1,1,-1};
int exdx[4]={0,0,d,-d};
int exdy[4]={d,-d,0,0};
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
a[i][j]=read();
if(a[i][j]==-1) startx=i,starty=j;
if(a[i][j]==-2) endx=i,endy=j;
if(a[i][j]>0)
{
int w=a[i][j],X;
for(int k=w;k>=0;k--)
{
X=w-k;
if(i+X<=n) p[i+X][max(1,j-k)]++;
if(i-X>=1) p[i-X][max(1,j-k)]++;
if(i+X<=n) p[i+X][min(m+1,j+k+1)]--;
if(i-X>=1) p[i-X][min(m+1,j+k+1)]--;
}
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
p[i][j]+=p[i][j-1];
bool flag=false;
int head=1,tail=1;
Q[tail].x=startx;
Q[tail].y=starty;
Q[tail].s=0;
Q[tail].r1=c1;
Q[tail].r2=c2;
book[startx][starty]=1;
tail++;
while(head<tail)
{
temp=Q[head];
if(temp.x==endx && temp.y==endy)
{
if(flag && anss<temp.s) break;
if(!flag) anss=temp.s,ansc1=c1-temp.r1,ansc2=c2-temp.r2,flag=true;
else if(ansc1+ansc2>c1-temp.r1+c2-temp.r2) ansc1=c1-temp.r1,ansc2=c2-temp.r2;
else if(ansc1+ansc2==c1-temp.r1+c2-temp.r2 && ansc1>c1-temp.r1) ansc1=c1-temp.r1,ansc2=c2-temp.r2;
}
for(int i=0;i<8;i++)
{
if(temp.x+dx[i]>=1 && temp.x+dx[i]<=n && temp.y+dy[i]>=1 && temp.y+dy[i]<=m
&& book[temp.x+dx[i]][temp.y+dy[i]]==0 && a[temp.x+dx[i]][temp.y+dy[i]]<=0)
{
if(p[temp.x+dx[i]][temp.y+dy[i]]!=0 && temp.r1>0)
{
Q[tail].x=temp.x+dx[i];
Q[tail].y=temp.y+dy[i];
Q[tail].s=temp.s+1;
Q[tail].r1=temp.r1-1;
Q[tail].r2=temp.r2;
tail++;
book[temp.x+dx[i]][temp.y+dy[i]]=1;
}
if(p[temp.x+dx[i]][temp.y+dy[i]]==0)
{
Q[tail].x=temp.x+dx[i];
Q[tail].y=temp.y+dy[i];
Q[tail].s=temp.s+1;
Q[tail].r1=temp.r1;
Q[tail].r2=temp.r2;
tail++;
book[temp.x+dx[i]][temp.y+dy[i]]=1;
}
}
}
for(int i=0;i<4;i++)
{
if(temp.x+exdx[i]>=1 && temp.x+exdx[i]<=n && temp.y+exdy[i]>=1 && temp.y+exdy[i]<=m
&& book[temp.x+exdx[i]][temp.y+exdy[i]]==0 && a[temp.x+exdx[i]][temp.y+exdy[i]]<=0)
{
if(p[temp.x+exdx[i]][temp.y+exdy[i]]!=0 && temp.r1>0)
{
Q[tail].x=temp.x+exdx[i];
Q[tail].y=temp.y+exdy[i];
Q[tail].s=temp.s+1;
Q[tail].r1=temp.r1-1;
Q[tail].r2=temp.r2-1;
tail++;
book[temp.x+exdx[i]][temp.y+exdy[i]]=1;
}
if(p[temp.x+exdx[i]][temp.y+exdy[i]]==0)
{
Q[tail].x=temp.x+exdx[i];
Q[tail].y=temp.y+exdy[i];
Q[tail].s=temp.s+1;
Q[tail].r1=temp.r1;
Q[tail].r2=temp.r2-1;
tail++;
book[temp.x+exdx[i]][temp.y+exdy[i]]=1;
}
}
}
head++;
}
if(!flag) cout<<-1<<endl;
else cout<<anss<<' '<<ansc1<<' '<<ansc2<<endl;
return 0;
}
```
by pengyule @ 2020-05-23 20:06:32
来自一位赛场上只用DFS拿了70分的蒟蒻的凝视并表示窝不会
by monstersqwq @ 2020-05-23 20:16:54
嗯,当时我调了一天,求助也没人管。
这种码农题基本没人会帮调的。
by ChthollyMeow @ 2020-05-23 20:36:39
虽然您求助地很好,但是这种码农题基本上没人帮您调的。。。
by 方123456 @ 2020-05-23 20:49:58
哦,好吧。谢谢大家了
by pengyule @ 2020-05-23 21:07:47
p.s.现在30pt...
by pengyule @ 2020-05-23 21:08:31