Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<vector>
- #include<stack>
- #include<set>
- #include<map>
- #include<queue>
- #include<deque>
- #include<string>
- #include<iostream>
- #include<algorithm>
- #include<cstring>
- #include<cassert>
- #include<cstdlib>
- #include<cstdio>
- #include<cmath>
- using namespace std;
- // Input macros
- #define s(n) scanf("%d",&n)
- #define sc(n) scanf("%c",&n)
- #define sl(n) scanf("%lld",&n)
- #define sf(n) scanf("%lf",&n)
- #define ss(n) scanf("%s",n)
- // Useful constants
- #define INF (int)1e9
- #define EPS 1e-9
- // Useful hardware instructions
- #define bitcount __builtin_popcount
- #define gcd __gcd
- // Useful container manipulation / traversal macros
- #define forall(i,a,b) for(int i=a;i<b;i++)
- #define foreach(v, c) for( typeof( (c).begin()) v = (c).begin(); v != (c).end(); ++v)
- #define whole(a) a.begin(), a.end()
- #define in(a,b) ( (b).find(a) != (b).end())
- #define pb push_back
- #define fill(a,v) memset(a, v, sizeof a)
- #define sz(a) ((int)(a.size()))
- #define mp make_pair
- // Some common useful functions
- #define maX(a,b) ( (a) > (b) ? (a) : (b))
- #define miN(a,b) ( (a) < (b) ? (a) : (b))
- #define checkbit(n,b) ( (n >> b) & 1)
- using namespace std;
- #if DEBUG && !ONLINE_JUDGE
- #define debug(args...) (Debugger()) , args
- class Debugger
- {
- public:
- Debugger(const std::string& _separator = ", ") :
- first(true), separator(_separator){}
- template<typename ObjectType>
- Debugger& operator , (const ObjectType& v)
- {
- if(!first)
- std:cerr << separator;
- std::cerr << v;
- first = false;
- return *this;
- }
- ~Debugger() { std:cerr << endl;}
- private:
- bool first;
- std::string separator;
- };
- template <typename T1, typename T2>
- inline std::ostream& operator << (std::ostream& os, const std::pair<T1, T2>& p)
- {
- return os << "(" << p.first << ", " << p.second << ")";
- }
- template<typename T>
- inline std::ostream &operator << (std::ostream & os,const std::vector<T>& v)
- {
- bool first = true;
- os << "[";
- for(unsigned int i = 0; i < v.size(); i++)
- {
- if(!first)
- os << ", ";
- os << v[i];
- first = false;
- }
- return os << "]";
- }
- template<typename T>
- inline std::ostream &operator << (std::ostream & os,const std::set<T>& v)
- {
- bool first = true;
- os << "[";
- for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end(); ++ii)
- {
- if(!first)
- os << ", ";
- os << *ii;
- first = false;
- }
- return os << "]";
- }
- template<typename T1, typename T2>
- inline std::ostream &operator << (std::ostream & os,const std::map<T1, T2>& v)
- {
- bool first = true;
- os << "[";
- for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end(); ++ii)
- {
- if(!first)
- os << ", ";
- os << *ii ;
- first = false;
- }
- return os << "]";
- }
- #else
- #define debug(args...) // Just strip off all debug tokens
- #endif
- typedef long long LL;
- typedef pair<int, int> PII;
- typedef pair<int, LL> PIL;
- typedef pair<LL, int> PLI;
- typedef pair<LL, LL> PLL;
- typedef vector<int> VI;
- typedef vector<LL> VL;
- typedef vector<vector<int> > VVI;
- typedef vector<VL> VVL;
- int ni()
- {
- int _num; s(_num);
- return _num;
- }
- /*-------------------------Main code begins now ------------------------------*/
- int testnum;
- typedef vector<string> VS;
- VS bestGrid, grid;
- int best;
- int N,M;
- int T[4][3][3] = { { {1,1,1},{0,1,0},{0,1,0}}, { {0,1,0},{0,1,0},{1,1,1}}, { {1,0,0},{1,1,1},{1,0,0}}, { {0,0,1},{1,1,1},{0,0,1}}};
- void preprocess()
- {
- }
- PII rotate(int x, int y, int dir)
- {
- if(dir == 0) return PII(x,y);
- if(dir == 1) return PII(-y, x);
- if(dir == 2) return PII(-x, -y);
- if(dir == 3) return PII(x,-y);
- }
- bool isValid(int r, int c)
- {
- return r >= 0 && c >=0 && r < N && c < M;
- }
- int solve(int pos, int n, VS grid)
- {
- int x = pos / 3, y = pos % 3;
- if(pos == N * M)
- {
- if(n > best)
- {
- best = n;
- bestGrid = VS(grid);
- debug("Best", best, bestGrid);
- }
- return 0;
- }
- int ans = 0;
- VS orig = VS(grid);
- for(int dir = 0; dir < 4; dir ++ )
- {
- grid = VS(orig);
- bool ok = true;
- for(int dx = -1; dx <= 1; dx++)
- for(int dy = -1;dy <= 1; dy++)
- {
- if(!isValid(x+dx, y+dy) || (T[dir][1+dx][1+dy] && grid[x+dx][y+dy] != '.'))
- ok = false;
- else if(T[dir][1+dx][1+dy])
- grid[x+dx][y+dy] = (char)('A' + n);
- }
- if(ok)
- ans = max(ans, 1 + solve(pos + 1, n+1,grid));
- }
- ans = max(ans, solve(pos+1, n, orig));
- return ans;
- }
- void solve()
- {
- best = 0;
- VS grid;
- grid.resize(N);
- forall(i, 0, N)
- {
- string s = "";
- forall(j, 0, M)
- s += '.';
- grid[i] = s;
- }
- solve(0,0,grid);
- cout << best << endl;
- forall(i,0,N)
- cout << bestGrid[i] << endl;
- }
- bool input()
- {
- s(N); s(M);
- return true;
- }
- int main()
- {
- preprocess();
- int T = 1;
- for(testnum=1;testnum<=T;testnum++)
- {
- if(!input()) break;
- solve();
- }
- }
Add Comment
Please, Sign In to add comment