В этой теме нет ответов

[LVP]

Автор темы: Рубиш Артур и Козлова Настя (7 класс)

Задача: Шахматный конь стоит на доске 8х8 в клетке х1, у1. Также на доске стоят K других фигур: на клетке a[i],b[i] стоит i-я фигура. Коню нужно добраться до клетки х2,у2 за наименьшее количество ходов.

Кроме очевидного способа решения задачи очередью, эту задачу можно сделать различными способами, которые я предоставил ниже.

1) Решение задачи стеком:

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define S second
#define F first
#define endl '\n'
#define pii pair < int, int >
using namespace std;

const int N = 3e5 + 10;
const int inf = 2e10;
const int smi[8] = {-2,-2,-1,-1,1,1,2,2}, smj[8] = {1,-1,2,-2,2,-2,-1,1};
int used[10][10], xx, yy;

void SOS(int x, int y)
{
//2.1.Функция SOS.
for (int i = 0;i < 8;i++)
{
xx = x + smi[i];
yy = y + smj[i];
//хх и уу – место, куда конь может встать.
if (xx >= 0 && xx < 8 && yy >= 0 && yy < 8 && used[xx][yy] == 0)
return;
//Если хх и уу не вылазят за доску и конь там ещё не был, ставим его туда.Иначе присваиваем в хх и уу -1.
}
xx = -1;
yy = -1;
}

int main()
{
for (int i = 0;i < 10;i++)
for (int j = 0;j < 10;j++)
used[i][j] = 0;
//1.Ввод.
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
x1--;y1--;x2--;y2--;
int n;
cin >> n;
int a[n], b[n];
for (int i = 0;i < n;i++)
{
cin >> a[i] >> b[i];
a[i]--; b[i]--;
used[a[i]][b[i]] = 1; //Помечаем i-го коня.
}
stack < pii > st;
used[x1][y1] = 1;
st.push({x1, y1});
//2,Основной код.
while (!st.empty() && !used[x2][y2])
{
int x = st.top().F, y = st.top().S; // х и у – место, где стоит конь сейчас.
SOS(x, y); //Функция находится в начале кода.
if (xx != -1)
{
st.push({xx, yy});
used[xx][yy] = 1;
//Если мы нашли хх и уу, ставим коня туда и помечаем место, где мы теперь стоим.
}
else st.pop();
}
//3.Вывод.Если клетка с номером х2.у2 помечена, выводим путь.
if (used[x2][y2] == 1)
{
cout << "Yes" << endl;
vector < pii > ans;
while (!st.empty())
{
ans.pb({st.top().F, st.top().S});
st.pop();
}
reverse(ans.begin(), ans.end());
for (auto to:ans)
cout << to.F + 1 << ' ' << to.S + 1 << endl;
}
else cout << "No";
}

2) Также можно решить эту задачу вектором:
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define S second
#define F first
#define endl '\n'
#define pii pair < int, int
using namespace std;
const int N = 3e5 + 10;
const int inf = 2e10;
const int smi[8] = {-2,-2,-1,-1,1,1,2,2}, smj[8] = {1,-1,2,-2,2,-2,-1,1};
int used[10][10], xx, yy;
void SOS(int x, int y)
{
//2.1.Функция SOS.
for (int i = 0;i < 8;i++)
{
xx = x + smi[i];
yy = y + smj[i];
if (xx >= 0 && xx < 8 && yy >= 0 && yy < 8 && used[xx][yy] == 0)
return;
}
//Если хх и уу не вылазят за доску и конь там ещё не был, ставим его туда.Иначе присваиваем в хх и уу -1.
xx = -1;
yy = -1;
}

int main()
{
for (int i = 0;i < 10;i++)
for (int j = 0;j < 10;j++)
used[i][j] = 0;
//1.Ввод.
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
x1--;y1--;x2--;y2--;
int n;
cin >> n;
int a[n], b[n];
for (int i = 0;i < n;i++)
{
cin >> a[i] >> b[i];
a[i]--;
b[i]--;
used[a[i]][b[i]] = 1; //Помечаем i-го коня.
}
vector < pii > st;
used[x1][y1] = 1;
st.push_back({x1, y1});
//2.Основной код.
while (!st.empty() && !used[x2][y2])
{
int x = st.back().F, y = st.back().S; // х и у – место, где стоит конь сейчас.
SOS(x, y); //Функция находится в начале кода.
if (xx != -1)
{
st.push_back({xx, yy});
used[xx][yy] = 1;
//Если мы нашли хх и уу, ставим коня туда и помечаем место, где мы теперь стоим.
}
else st.pop_back();
}
//3.Вывод.Если клетка с номером х2.у2 помечена, выводим путь.
if (used[x2][y2] == 1)
{
cout << "Yes" << endl;
for (auto to:st)
cout << to.F + 1 << ' ' << to.S + 1 << endl;
}
else cout << "No";
}

3) решение задачи рекурсией:
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define S second
#define F first
#define endl '\n'
#define pii pair < int, int >

using namespace std;
const int N = 3e5 + 10;
const int inf = 2e10;
const int smi[8] = {-2,-2,-1,-1,1,1,2,2}, smj[8] = {1,-1,2,-2,2,-2,-1,1};
int used[10][10], xx, yy, x1, y1, x2, y2;
stack < pii > st;

void SOS(int x, int y)
{
if (used[x2][y2] == 1)
return;
//Если финишная клетка уже помечена, останавливаем рекурсию.
for (int i = 0;i < 8;i++)
{
xx = x + smi[i];
yy = y + smj[i];
if (xx >= 0 && xx < 8 && yy >= 0 && yy < 8 && used[xx][yy] == 0 && used[x2][y2] == 0)
{
st.push({xx, yy});
used[xx][yy] = 1;
SOS(xx, yy);
//Если мы нашли хх и уу, ставим коня туда,помечаем место, где мы теперь стоим и заново запускаем рекурсию.
}
}
if (used[x2][y2] == 0) st.pop();
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for (int i = 0;i < 10;i++)
for (int j = 0;j < 10;j++)
used[i][j] = 0;
//1.Ввод.
cin >> x1 >> y1 >> x2 >> y2;
x1--;y1--;x2--;y2--;
int n;
cin >> n;
int a[n], b[n];
for (int i = 0;i < n;i++)
{
cin >> a[i] >> b[i];
a[i]--;
b[i]--;
used[a[i]][b[i]] = 1;//Помечаем i-го коня.
}
used[x1][y1] = 1;
st.push({x1, y1});
SOS(x1, y1);//Функция находится в начале кода.
//3.Вывод.Если клетка с номером х2.у2 помечена, выводим путь.
if (used[x2][y2] == 1)
{
cout << "Yes" << endl;
vector < pii > ans;
while (!st.empty())
{
ans.pb({st.top().F, st.top().S});
st.pop();
}
reverse(ans.begin(), ans.end());
for (auto to:ans)
cout << to.F + 1 << ' ' << to.S + 1 << endl;
}
else cout << "No";
}

4) решение задачи очередью от
Анастасии Козловой (7 класс)
#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
using namespace std;
int q[2][100000],a[110][110], uk,un,i,j;
void sos(int x, int y)
{
if (a[x][y]==0)
{
a[x][y]=a[i][j]+1;
q[0][uk]=x;
q[1][uk]=y;
uk++;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int n,m,x1,x2,y1,y2;
char z[110][110];
cin»n;
//int m;
cin»m;
for(int t=2; t<=n+1; t++)
for(int h=2; h<=m+1; h++)
{
cin»z[t][h];
if (z[t][h]=='X')
a[t][h]=-1;
else
a[t][h]=0;
if (z[t][h]=='S')
{
x1=t;
y1=h;
}
if (z[t][h]=='F')
{
x2=t;
y2=h;
}

}
for(int i=0; i<=n+3; i++)
{
a[i][0]=-1;
a[i][1]=-1;
a[i][m+2]=-1;
a[i][m+3]=1;
}
for(int i=0; i<=m+3; i++)
{
a[0][i]=-1;
a[1][i]=-1;
a[n+2][i]=-1;
a[n+3][i]=-1;
}
un=0;
uk=1;
q[0][0]=x1;
q[1][0]=y1;
a[x1][y1]=1;
while (uk>un && a[x2][y2]==0)
{
i=q[0][un];
j=q[1][un];
un++;
sos(i+1,j+2);
sos(i-1,j-2);
sos(i+2,j+1);
sos(i-2,j-1);
sos(i-1,j+2);
sos(i+1,j-2);
sos(i+2,j-1);
sos(i-2,j+1);
}
//cout«a[x2][y2]«' '«x2«' '«y2«' '«endl;
vector<pair<int, int> > ans;
if (a[x2][y2]!=0)
cout«"Yes" « endl;
else
{
cout«"No"«endl;
return 0;
}
int k=a[x2][y2];
for(int l=k; l>=2; l--)
{
ans.pb({x2-1,y2-1});
if (a[x2-1][y2-2]==l-1)
{
x2--;
y2-=2;
}
else
if (a[x2+1][y2+2]==l-1)
{
x2++;
y2+=2;
}
else
if (a[x2-1][y2+2]==l-1)
{
x2--;
y2+=2;
}
else
if (a[x2+1][y2-2]==l-1)
{
x2++;
y2-=2;
}
else
if (a[x2-2][y2-1]==l-1)
{
x2-=2;
y2--;
}
else
if (a[x2+2][y2+1]==l-1)
{
x2+=2;
y2++;
}
else
if (a[x2-2][y2+1]==l-1)
{
x2-=2;
y2++;
}
else
if (a[x2+2][y2-1]==l-1)
{
x2+=2;
y2--;
}
}
reverse(ans.begin(),ans.end());
for(int o = 0; o<ans.size(); o++)
cout«ans[o].F«' '«ans[o].S«endl;
return 0;
}