Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <string>
- #include <stack>
- #include <set>
- #include <map>
- #define pii pair <int,int>
- #define vec vector
- using namespace std;
- using ll = long long;
- using ld = long double;
- using db = double;
- void cv(vector <int> &v){
- for (auto x: v) cout<<x<<' ';
- cout<<"\n";
- }
- void cvl(vector <ll> &v){
- for (auto x: v) cout<<x<<' ';
- cout<<"\n";
- }
- void cvv(vector <vector <int> > &v){
- for (auto x: v) cv(x);
- cout<<"\n";
- }
- vector < vector < vector<pii> > > G;
- //vector[0] - слева - пара (x,y)
- //vec[1] - справа
- //vec[2] - сверху
- //vec[3] - снизу
- vector <vector<int>> dsk;
- vector <vector <int> > dist;
- const int inf = 2e9;
- int n,m;
- bool gd(pii x){
- return x.first >= 0 && x.first < n && x.second >= 0 && x.second < m && dsk[x.first][x.second] != 1;
- }
- void shG(){
- for (int i=0;i<n;++i){
- for (int j=0;j<m;++j){
- cout<<"("<<i<<","<<j<<") \n";
- for (int k = 0;k<4;++k){
- cout<<G[i][j][k].first<<' '<<G[i][j][k].second<<"\n";
- }
- }
- }cout<<"\n";
- }
- void shdsk(){
- for (int i=0;i<n;++i){
- for (int j=0;j<m;++j){
- cout<<dsk[i][j]<<' ';
- }cout<<"\n";
- }cout<<"\n";
- }
- int main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- //cin>>n>>m;
- n = 18;
- m = 14;
- dist.resize(n, vector <int> (m , inf));
- dsk.resize(n, vector <int>(m,0));
- for (int i=0;i<n;++i){
- for (int j=0;j<m;++j) continue ;//cin>>dsk[i][j];
- }
- //строим G
- for (int i = 1; i <= 7;++i) dsk[i][0] = 1;
- for (int j = 5; j<=9;++j) dsk[0][j] = 1;
- for (int i=0;i<=7;++i) dsk[i][7] = 1;
- for (int i = 1;i<=3;++i) dsk[i][10] =1;
- for (int j = 1;j<=6;++j) dsk[9][j] = 1;
- for (int i=5;i<=9;++i) dsk[i][10] = 1;
- for (int j=8;j<=10;++j) dsk[9][j] = 1;
- for (int i=4;i<=8;++i) dsk[i][12] = 1;
- for (int j=3;j<=4;++j) dsk[13][j] = 1;
- vector <pii> pnt = { {14, 2}, {14, 5}, {15, 4}, {16, 6}, {12, 12}, {13, 11}, {14, 10}, {15, 9}, {15, 12}, {16, 11} };
- for (int i=0;i<pnt.size();++i){
- dsk[pnt[i].first][pnt[i].second] = 1;
- }
- shdsk();
- G.resize(n, vector <vector <pii> > (m, vector <pii> (4, {-1, -1})));
- pii str = {0,0};
- pii v = str;
- //заполняем v[1] и v[3] для (0,0)
- while (gd({v.first, v.second+1})){
- v.second++;
- if (dsk[v.first][v.second] == 2){
- cout<<1<<"\n";
- exit(0);
- }
- }
- G[0][0][1] = v;
- G[v.first][v.second][0] = {0,0};
- v = str;
- while (gd({v.first+1, v.second})){
- v.first++;
- if (dsk[v.first][v.second] == 2){
- cout<<1<<"\n";
- exit(0);
- }
- }
- G[0][0][3] = v;
- G[v.first][v.second][2] = {0,0};
- //vector[0] - слева
- //vec[1] - справа
- //vec[2] - сверху
- //vec[3] - снизу
- shG();
- //план такой: сначала отметить ребра от (0,0) до 2-х доступных точек (вершин) - OK
- //потом отметить расстояния от всех получившихся (2-х - 3-х вершин) ребра до остальных доступных точек (КАК - это надо додоумать)
- //запуститься из (0,0)
- }
- /*
- 4 5
- 0 0 0 0 1
- 0 1 1 0 2
- 0 2 1 2 0
- 0 0 1 0 0
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement