Консультации

optimization

optimization

от Nurlibek Aimagambetov -
Number of replies: 1
Hello.
Please, answer how can I shorten my code?
# include
# include
# include
# include
# include
# include
# include
# include
# include
# include
# include
# include
# include
# include
# include
# include
# include
# include
# include
# include

#define mp make_pair

using namespace std;

typedef long long ll;

ll n;
vector >g[21][21];
ll d[21][21];
pair p[21][21];

void work(ll x,ll y,ll a,ll b)
{
if (x>=0&&x=0&&y {
g[x][y].push_back(mp(a,b));
}
}

int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin>>n;
ll x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
--x1,--y1,--x2,--y2;
for(ll i=0;i {
for(ll j=0;j {
work(i+2,j+1,i,j);
work(i+2,j-1,i,j);
work(i+1,j+2,i,j);
work(i+1,j-2,i,j);
work(i-1,j+2,i,j);
work(i-1,j-2,i,j);
work(i-2,j+1,i,j);
work(i-2,j-1,i,j);
}
}
queue >q;
pair p[21][21];
q.push(mp(x1,y1));
p[x1][y1]=mp(22,22);
d[x1][y1]=0;
bool u[21][21];

while(q.size())
{
pairv=q.front();
q.pop();
u[v.first][v.second]=1;
ll v1,v2;
v1=v.first;
v2=v.second;
for(ll i=0;i {
pairto=g[v1][v2][i];
ll to1=to.first;
ll to2=to.second;
if (!u[to1][to2])
{
q.push(mp(to1,to2));
u[to1][to2]=1;
d[to1][to2]=d[v1][v2]+1;
p[to1][to2]=mp(v1,v2);
}
}
}
cout< vector >ans;
for(pairf=mp(x2,y2);f.first!=22;f=p[f.first][f.second])
{
ans.push_back(mp(f.first,f.second));

}
reverse(ans.begin(),ans.end());
for(ll i=0;i {
cout< }
return 0;
}
105 строк
In reply to Nurlibek Aimagambetov

Re: optimization

от Peter Cherepanov -
Есть много способов. Один программист-практик утверждал, что любую программу можно сократить на 1 строчку не изменяя результата.

В вашем случае я бы прежде всего выкинул C++ .
Достижимые поля можно представить 64-битовым вектором, который помещается в тип long long. Значит, массивы не нужны вообще.
Далее, опрерациями сдвига и логического сложения можно найти достижимые поля после каждого шага.
И продолжать так, пока конечное поле не будет достигнуто.

По сути, такая программа моделирует недетерминированный автомат, который принимает множество состояний сразу.

Похожее решение выбрано как лучшее решение для задачи № 163. "Два коня". Решите ее любым способом и смотрите решение.