Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define FRE(i,a,b) for(i = a; i <= b; i++)
- #define FRL(i,a,b) for(i = a; i < b; i++)
- #define mem(t, v) memset ((t) , v, sizeof(t))
- #define all(x) x.begin(),x.end()
- #define un(x) x.erase(unique(all(x)), x.end())
- #define sf(n) scanf("%d", &n)
- #define sff(a,b) scanf("%d %d", &a, &b)
- #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
- #define sl(n) scanf("%lld", &n)
- #define sll(a,b) scanf("%lld %lld", &a, &b)
- #define slll(a,b,c) scanf("%lld %lld %lld", &a, &b, &c)
- #define D(x) cerr << #x " = " << (x) << '\n'
- #define DBG cerr << "Hi" << '\n'
- #define pb push_back
- #define PI acos(-1.00)
- #define xx first
- #define yy second
- #define eps 1e-9
- typedef unsigned long long int ULL;
- typedef long long int LL;
- typedef pair<int,int> pii;
- typedef pair<LL,LL> pll;
- inline int setBit(int N, int pos) { return N=N | (1<<pos); }
- inline int resetBit(int N, int pos) { return N= N & ~(1<<pos); }
- inline bool checkBit(int N, int pos) { return (bool)(N & (1<<pos)); }
- //int fx[] = {+0, +0, +1, -1, -1, +1, -1, +1};
- //int fy[] = {-1, +1, +0, +0, +1, +1, -1, -1}; //Four & Eight Direction
- int ways;
- int kx[30], ky[30];
- bool vis[210][210];
- int n, m, filled, options[210][210], distFromCentre[210][210];
- pii centre;
- vector<pii> sltn;
- inline bool ok(int r, int c)
- {
- if(r >= 0 && r < n && c >= 0 && c < m && vis[r][c] == false)
- return true;
- return false;
- }
- void init()
- {
- centre.xx = (n+1)/2 - 1;
- centre.yy = (m+1)/2 - 1;
- ways = 0;
- for(int x = -3; x<=3; x++)
- {
- for(int y = -3; y<=3; y++)
- {
- int sum = abs(x) + abs(y);
- if(sum == 2 || sum == 3)
- {
- kx[ways] = x;
- ky[ways] = y;
- ways++;
- }
- }
- }
- for(int i = 0; i<n; i++)
- {
- for(int j = 0; j<m; j++)
- {
- for(int d = 0; d<ways; d++)
- {
- options[i][j] += ok(i+kx[d], j+ky[d]);
- }
- distFromCentre[i][j] = abs(centre.xx - i) + abs(centre.yy - j);
- }
- }
- }
- inline bool cmp(pii a, pii b)
- {
- if(options[a.xx][a.yy] == options[b.xx][b.yy])
- {
- if(distFromCentre[a.xx][a.yy] < distFromCentre[b.xx][b.yy])
- return true;
- else
- return false;
- }
- return options[a.xx][a.yy] < options[b.xx][b.yy];
- }
- inline void update(int r, int c, int v)
- {
- filled += v;
- if(v == 1)
- vis[r][c] = true;
- else
- vis[r][c] = false;
- for(int d = 0; d<ways; d++)
- {
- pii nw = {r+kx[d], c+ky[d]};
- if(ok(nw.xx,nw.yy))
- options[nw.xx][nw.yy] += v;
- }
- }
- bool backtrack(int r, int c)
- {
- // cout << r << " " << c << endl;
- update(r,c,1);
- vector<pii> nxt;
- for(int d = 0; d<ways; d++)
- {
- pii nw = {r+kx[d], c+ky[d]};
- if(ok(nw.xx,nw.yy))
- nxt.pb(nw);
- }
- if(nxt.size() == 0)
- {
- if(filled == n*m && ((r+c) == 2 || (r+c) == 3))
- {
- sltn.pb({r,c});
- return true;
- }
- update(r,c,-1);
- return false;
- }
- sort(all(nxt),cmp);
- for(int i = 0; i<nxt.size(); i++)
- {
- if(backtrack(nxt[i].xx, nxt[i].yy))
- {
- sltn.pb({r,c});
- return true;
- }
- }
- update(r,c,-1);
- return false;
- }
- int main()
- {
- //freopen("in.txt","r",stdin);
- //freopen("out.txt","w",stdout);
- int i, j, cs, t;
- sff(n,m);
- init();
- if(backtrack(0,0))
- {
- for(int i = (int)sltn.size()-1; i>=0; i--)
- printf("%d %d\n",sltn[i].xx+1,sltn[i].yy+1);
- }
- else
- puts("-1");
- return 0;
- }
Add Comment
Please, Sign In to add comment