81分求助
- 板块P1930 [USACO3.3] 亚瑟王的宫殿
- 楼主Zizhou880
- 当前回复0
- 已保存回复0
- 发布时间2024/11/27 21:34
- 上次更新2024/11/28 08:21:49
查看原帖
被骇客银狼阻止的越权访问保存失败
81分求助
#include<bits/stdc++.h>
#include<bitset>
#define int long
#define INF 0x3f3f3f3f
using namespace std;
int x=0,y,z,r,c,k=1,ans=0,cnt=0,mans=INF,mx,my,lk,kkx,kky,kkxx,kkyy;
char a;
int b;
short dis[100][100][100][100];//骑士到终点的距离
bool sit[50][50];
bool king[50][50];
bool aim[50][50];//任意bfs终点
queue<int> qx;
queue<int> qy;
vector<int> vx;
vector<int> vy;//终点位置s
vector<int> kx;
vector<int> ky;//骑士位置
vector<int> kdis;
//int kdis;//骑士到王的距离
bitset<50> vis[50];
priority_queue<int,vector<int>,greater<int> > ex;//最少额外花费
priority_queue<int,vector<int>,greater<int> > fnl;//答案
int dir[10][2]={{-1,-2},{-1,2},{-2,-1},{-2,1},{1,-2},{1,2},{2,-1},{2,1}};
void bfs(int x,int y)
{
qx.push(x);qy.push(y);
qx.push(-1);qy.push(-1);
vis[x][y]=1;
while(qx.size()!=1)
{
if(qx.front()==-1)
{
cnt++;
qx.push(-1);
qy.push(-1);
qx.pop();
qy.pop();
continue;
}
if(sit[qx.front()][qy.front()]==1)
{
dis[x][y][qx.front()][qy.front()]=cnt;
ans+=cnt;
}
for(int i=0;i<=7;i++)
{
if(qx.front()+dir[i][0]>0&&qx.front()+dir[i][0]<=c&&qy.front()+dir[i][1]>0&&qy.front()+dir[i][1]<=r&&vis[qx.front()+dir[i][0]][qy.front()+dir[i][1]]!=true)
{
qx.push(qx.front()+dir[i][0]);
qy.push(qy.front()+dir[i][1]);
vis[qx.front()+dir[i][0]][qy.front()+dir[i][1]]=true;
}
}
qx.pop();qy.pop();
}
}
int bfs_k(int x,int y,int p,int q)//(x,y) -> (p,q)
{
aim[p][q]=1;
ans=0;cnt=0;
qx.push(x);qy.push(y);
qx.push(-1);qy.push(-1);
vis[x][y]=1;
while(qx.front()!=-1||qx.back()!=-1)
{
if(qx.front()==-1)
{
qx.push(-1);
qy.push(-1);
cnt++;
qx.pop();
qy.pop();
continue;
}
if(aim[qx.front()][qy.front()]==1)
{
ans=cnt;
break;
}
for(int i=0;i<=7;i++)
{
if(qx.front()+dir[i][0]>0&&qx.front()+dir[i][0]<=c&&qy.front()+dir[i][1]>0&&qy.front()+dir[i][1]<=r&&vis[qx.front()+dir[i][0]][qy.front()+dir[i][1]]!=true)
{
qx.push(qx.front()+dir[i][0]);
qy.push(qy.front()+dir[i][1]);
vis[qx.front()+dir[i][0]][qy.front()+dir[i][1]]=true;
}
}
qx.pop();qy.pop();
}
aim[p][q]=0;
while(!qx.empty()) qx.pop();
while(!qy.empty()) qy.pop();
for(int i=1;i<=c;i++)
vis[i].reset();
return ans;
}
signed main()
{
cin>>c>>r;
while(cin>>a>>b)
{
if(z==0)
{
z=1;
king[b][a-'A'+1]=1;
kkx=b;kky=a-'A'+1;
}
else
{
sit[b][a-'A'+1]=1;
kx.push_back(b);
ky.push_back(a-'A'+1);
}
}
if(kx.empty())
{
cout<<0<<endl;
return 0;
}
for(int i=1;i<=c;i++)
for(int j=1;j<=r;j++)
{
bfs(i,j);
if(mans==ans)
{
vx.push_back(i);
vy.push_back(j);
}
if(mans>ans)
{
mans=ans;
mx=i;
my=j;
vx.clear();
vy.clear();
vx.push_back(i);
vy.push_back(j);
}
qx.pop();qy.pop();
cnt=0;ans=0;
for(int i=1;i<=c;i++)
vis[i].reset();
}
kkxx=kkx;kkyy=kky;
for(int m=-5;m<=5;m++)
for(int n=-5;n<=5;n++)
{
kkx=kkxx+m;
kky=kkyy+n;
if(kkx<1||kky<1)
continue;
if(kkx>r||kky>c)
continue;
for(int i=0;i<=kx.size()-1;i++)
{
kdis.push_back(bfs_k(kx[i],ky[i],kkx,kky));
}
for(int i=0;i<=vx.size()-1;i++)
{
lk=bfs_k(kkx,kky,vx[i],vy[i]);
for(int j=0;j<=kx.size()-1;j++)
{
ex.push(kdis[j]+lk-dis[vx[i]][vy[i]][kx[j]][ky[j]]+max(abs(m),abs(n)));
}
}
kdis.clear();
}
cout<<mans+ex.top()<<endl;
return 0;
}
错了第7和第11个点，额外花费总是算出来负数，下面是调试用代码
#include<bits/stdc++.h>
#include<bitset>
#define int long
#define INF 0x3f3f3f3f
using namespace std;
int x=0,y,z,r,c,k=1,ans=0,cnt=0,mans=INF,mx,my,lk,kkx,kky,kkxx,kkyy;
char a;
int b;
short dis[100][100][100][100];//骑士到终点的距离
bool sit[50][50];
bool king[50][50];
bool aim[50][50];//任意bfs终点
queue<int> qx;
queue<int> qy;
vector<int> vx;
vector<int> vy;//终点位置s
vector<int> kx;
vector<int> ky;//骑士位置
vector<int> kdis;
//int kdis;//骑士到王的距离
bitset<50> vis[50];
priority_queue<int,vector<int>,greater<int> > ex;//最少额外花费
priority_queue<int,vector<int>,greater<int> > fnl;//答案
int dir[10][2]={{-1,-2},{-1,2},{-2,-1},{-2,1},{1,-2},{1,2},{2,-1},{2,1}};
void bfs(int x,int y)
{
qx.push(x);qy.push(y);
qx.push(-1);qy.push(-1);
vis[x][y]=1;
while(qx.size()!=1)
{
// cout<<char(qx.front()-1+'A')<<" "<<qy.front()<<endl;
if(qx.front()==-1)
{
cnt++;
qx.push(-1);
qy.push(-1);
qx.pop();
qy.pop();
continue;
}
if(sit[qx.front()][qy.front()]==1)
{
dis[x][y][qx.front()][qy.front()]=cnt;
ans+=cnt;
}
for(int i=0;i<=7;i++)
{
if(qx.front()+dir[i][0]>0&&qx.front()+dir[i][0]<=c&&qy.front()+dir[i][1]>0&&qy.front()+dir[i][1]<=r&&vis[qx.front()+dir[i][0]][qy.front()+dir[i][1]]!=true)
{
qx.push(qx.front()+dir[i][0]);
qy.push(qy.front()+dir[i][1]);
vis[qx.front()+dir[i][0]][qy.front()+dir[i][1]]=true;
}
}
qx.pop();qy.pop();
}
}
int bfs_k(int x,int y,int p,int q)//(x,y) -> (p,q)
{
for(int ii=1;ii<=r;ii++)
{
for(int jj=1;jj<=c;jj++)
cout<<vis[ii][jj]<<" ";
cout<<endl;
}
aim[p][q]=1;
ans=0;cnt=0;
qx.push(x);qy.push(y);
qx.push(-1);qy.push(-1);
vis[x][y]=1;
while(qx.size()!=1)
{
if(qx.front()==-1)
{
qx.push(-1);
qy.push(-1);
cnt++;
qx.pop();
qy.pop();
continue;
}
if(aim[qx.front()][qy.front()]==1)
{
ans=cnt;
break;
}
for(int ii=0;ii<=7;ii++)
{
if(qx.front()+dir[ii][0]>0&&qx.front()+dir[ii][0]<=c&&qy.front()+dir[ii][1]>0&&qy.front()+dir[ii][1]<=r&&vis[qx.front()+dir[ii][0]][qy.front()+dir[ii][1]]!=true)
{
qx.push(qx.front()+dir[ii][0]);
qy.push(qy.front()+dir[ii][1]);
vis[qx.front()+dir[ii][0]][qy.front()+dir[ii][1]]=true;
}
}
cout<<char(qx.front()+'A'-1)<<" "<<qy.front()<<endl;
cout<<char(qx.back()+'A'-1)<<" "<<qy.back()<<endl;
cout<<qx.front()<<" "<<qy.front()<<endl;
cout<<qx.size()<<endl;
qx.pop();qy.pop();
}
aim[p][q]=0;
while(!qx.empty()) qx.pop();
while(!qy.empty()) qy.pop();
for(int ii=1;ii<=r;ii++)
for(int jj=1;jj<=c;jj++)
vis[ii][jj]=0;
return ans;
}
signed main()
{
cin>>r>>c;
while(cin>>a>>b)
{
if(z==0)
{
z=1;
king[a-'A'+1][b]=1;
kkx=a-'A'+1;kky=b;
}
else
{
sit[a-'A'+1][b]=1;
kx.push_back(a-'A'+1);
ky.push_back(b);
}
}
if(kx.empty())
{
cout<<0<<endl;
return 0;
}
cout<<endl<<endl<<endl;
cout<<bfs_k(25,1,1,1);////HERE
cout<<endl<<endl<<endl;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
bfs(j,i);
if(mans==ans)
{
vx.push_back(j);
vy.push_back(i);
}
if(mans>ans&&ans>0)
{
mans=ans;
mx=j;
my=i;
vx.clear();
vy.clear();
vx.push_back(j);
vy.push_back(i);
}
while(!qx.empty())
{
qx.pop();qy.pop();
}
cnt=0;ans=0;
// cout<<mans<<endl;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
vis[i][j]=0;
}
for(int i=1;i<=r;i++)
vis[i].reset();
kkxx=kkx;kkyy=kky;
for(int m=-5;m<=5;m++)
for(int n=-5;n<=5;n++)
{
kkx=kkxx+m;
kky=kkyy+n;
if(kkx<1||kky<1)
continue;
if(kkx>c||kky>r)
continue;
for(int i=0;i<=kx.size()-1;i++)
{
kdis.push_back(bfs_k(kx[i],ky[i],kkx,kky));
}
for(int i=0;i<=vx.size()-1;i++)
{
lk=bfs_k(kkx,kky,vx[i],vy[i]);
for(int j=0;j<=kx.size()-1;j++)
{
// if(kdis[j]+lk-dis[vx[i]][vy[i]][kx[j]][ky[j]]+max(abs(m),abs(n))>0)
ex.push(kdis[j]+lk-dis[vx[i]][vy[i]][kx[j]][ky[j]]+max(abs(m),abs(n)));
cout<<kdis[j]<<" "<<lk<<" "<<dis[vx[i]][vy[i]][kx[j]][ky[j]]<<" "<<max(abs(m),abs(n))<<" ";
}
cout<<ex.top()<<endl;
}
kdis.clear();
}
// cout<<mans<<endl;
// if(ex.top()>0)
cout<<mans+ex.top()<<endl;
// else
// cout<<mans<<endl;
// cout<<ex.size()<<endl;
cout<<bfs_k(25,1,1,1);
return 0;
}
这里面bfs_k在"HERE"前能用,后面就直接不push了
第一道蓝题，求解答
加载中...