标签：q1 int Move 3005 cc Snake && empty
- 赛后独立思考了不算长的一段时间，然后就通过了；赛时没看这道题有些可惜，算是个教训吧
- 发现两个性质之后，这道题就非常简单了：
1.只有初始位置的贪吃蛇才可能会对最优路径产生影响
2.令贪吃蛇长度-1的操作等价于它停在原地不动
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int a[3005][3005];
int f[3005][3005];
int read1()
{
char cc=getchar();
while(!(cc>=48&&cc<=57))
{
if(cc=='-')
{
break;
}
cc=getchar();
}
bool f=false;
int s=0;
if(cc=='-')
{
f=true;
}
else
{
s=cc-48;
}
while(1)
{
cc=getchar();
if(cc>=48&&cc<=57)
{
s=s*10+cc-48;
}
else
{
break;
}
}
if(f==true)
{
s=-s;
}
return s;
}
struct t1
{
int x,y,w;
};
bool operator <(t1 a,t1 b)
{
if(a.w!=b.w)
{
return a.w<b.w;
}
else if(a.x!=b.x)
{
return a.x<b.x;
}
return a.y<b.y;
}
priority_queue<t1>q;
deque<pair<int,int> >q1;
deque<int>q2;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
void bfs(int s,int t)
{
f[s][t]=0;
q1.push_back(make_pair(s,t));
q2.push_back(0);
while(!(q1.empty()&&q.empty()))
{
if(q1.empty()||!q.empty()&&-q.top().w<=q2.front())
{
t1 tmp=q.top();
q.pop();
q1.push_front(make_pair(tmp.x,tmp.y));
q2.push_front(-tmp.w);
}
int x=q1.front().first,y=q1.front().second;
q1.pop_front();
int w=q2.front();
q2.pop_front();
for(int i=0;i<4;i++)
{
if(w>=a[x+dx[i]][y+dy[i]]&&w+1<f[x+dx[i]][y+dy[i]])
{
f[x+dx[i]][y+dy[i]]=w+1;
q1.push_back(make_pair(x+dx[i],y+dy[i]));
q2.push_back(w+1);
}
else if(a[x+dx[i]][y+dy[i]]!=INT_MAX&&w+1<f[x+dx[i]][y+dy[i]])
{
t1 tmp;
tmp.x=x;tmp.y=y;tmp.w=-a[x+dx[i]][y+dy[i]];
q.push(tmp);
}
}
}
}
int main()
{
int n,m,k;
cin>>n>>m>>k;
int s,t;
for(int i=1;i<=k;i++)
{
int x,y;
x=read1();
y=read1();
if(i==1)
{
s=x;
t=y;
}
a[x][y]=k-i;
}
string S;
for(int i=1;i<=n;i++)
{
cin>>S;
for(int j=1;j<=m;j++)
{
if(a[i][j]==0)
{
if(S[j-1]=='.')
{
a[i][j]=0;
}
else
{
a[i][j]=INT_MAX;
}
}
a[0][j]=a[n+1][j]=INT_MAX;
}
a[i][0]=a[i][m+1]=INT_MAX;
}
memset(f,0x3f,sizeof(f));
bfs(s,t);
unsigned long long ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
long long tmp=f[i][j];
if(f[i][j]<1000000000)
{
ans=ans+tmp*tmp;
}
}
}
cout<<ans<<endl;
return 0;
}
标签：q1,
int,
Move,
3005,
cc,
Snake,
&&,
empty
From： https://www.cnblogs.com/watersail/p/17985706