Guest User

Untitled

a guest
May 22nd, 2018
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.98 KB | None | 0 0
  1. #include<vector>
  2. #include<stack>
  3. #include<set>
  4. #include<map>
  5. #include<queue>
  6. #include<deque>
  7. #include<string>
  8. #include<iostream>
  9. #include<algorithm>
  10. #include<cstring>
  11. #include<cassert>
  12. #include<cstdlib>
  13. #include<cstdio>
  14. #include<cmath>
  15.  
  16. using namespace std;
  17.  
  18. // Input macros
  19. #define s(n)                        scanf("%d",&n)
  20. #define sc(n)                       scanf("%c",&n)
  21. #define sl(n)                       scanf("%lld",&n)
  22. #define sf(n)                       scanf("%lf",&n)
  23. #define ss(n)                       scanf("%s",n)
  24.  
  25. // Useful constants
  26. #define INF                         (int)1e9
  27. #define EPS                         1e-9
  28.  
  29. // Useful hardware instructions
  30. #define bitcount                    __builtin_popcount
  31. #define gcd                         __gcd
  32.  
  33. // Useful container manipulation / traversal macros
  34. #define forall(i,a,b)               for(int i=a;i<b;i++)
  35. #define foreach(v, c)               for( typeof( (c).begin()) v = (c).begin();  v != (c).end(); ++v)
  36. #define whole(a)                    a.begin(), a.end()
  37. #define in(a,b)                     ( (b).find(a) != (b).end())
  38. #define pb                          push_back
  39. #define fill(a,v)                   memset(a, v, sizeof a)
  40. #define sz(a)                       ((int)(a.size()))
  41. #define mp                          make_pair
  42.  
  43. // Some common useful functions
  44. #define maX(a,b)                    ( (a) > (b) ? (a) : (b))
  45. #define miN(a,b)                    ( (a) < (b) ? (a) : (b))
  46. #define checkbit(n,b)               ( (n >> b) & 1)
  47.  
  48. using namespace std;
  49.  
  50. #if DEBUG && !ONLINE_JUDGE
  51.  
  52.     #define debug(args...)     (Debugger()) , args
  53.  
  54.     class Debugger
  55.     {
  56.         public:
  57.         Debugger(const std::string& _separator = ", ") :
  58.         first(true), separator(_separator){}
  59.  
  60.         template<typename ObjectType>
  61.         Debugger& operator , (const ObjectType& v)
  62.         {
  63.             if(!first)
  64.                 std:cerr << separator;
  65.             std::cerr << v;
  66.             first = false;
  67.             return *this;
  68.         }
  69.         ~Debugger() {  std:cerr << endl;}
  70.  
  71.         private:
  72.         bool first;
  73.         std::string separator;
  74.     };
  75.  
  76.     template <typename T1, typename T2>
  77.     inline std::ostream& operator << (std::ostream& os, const std::pair<T1, T2>& p)
  78.     {
  79.         return os << "(" << p.first << ", " << p.second << ")";
  80.     }
  81.  
  82.     template<typename T>
  83.     inline std::ostream &operator << (std::ostream & os,const std::vector<T>& v)
  84.     {
  85.         bool first = true;
  86.         os << "[";
  87.         for(unsigned int i = 0; i < v.size(); i++)
  88.         {
  89.             if(!first)
  90.                 os << ", ";
  91.             os << v[i];
  92.             first = false;
  93.         }
  94.         return os << "]";
  95.     }
  96.  
  97.     template<typename T>
  98.     inline std::ostream &operator << (std::ostream & os,const std::set<T>& v)
  99.     {
  100.         bool first = true;
  101.         os << "[";
  102.         for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end(); ++ii)
  103.         {
  104.             if(!first)
  105.                 os << ", ";
  106.             os << *ii;
  107.             first = false;
  108.         }
  109.         return os << "]";
  110.     }
  111.  
  112.     template<typename T1, typename T2>
  113.     inline std::ostream &operator << (std::ostream & os,const std::map<T1, T2>& v)
  114.     {
  115.         bool first = true;
  116.         os << "[";
  117.         for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end(); ++ii)
  118.         {
  119.             if(!first)
  120.                 os << ", ";
  121.             os << *ii ;
  122.             first = false;
  123.         }
  124.         return os << "]";
  125.     }
  126.  
  127. #else
  128.     #define debug(args...)                  // Just strip off all debug tokens
  129. #endif
  130.  
  131. typedef long long LL;
  132.  
  133. typedef pair<int, int> PII;
  134. typedef pair<int, LL> PIL;
  135. typedef pair<LL, int> PLI;
  136. typedef pair<LL, LL> PLL;
  137.  
  138. typedef vector<int> VI;
  139. typedef vector<LL> VL;
  140. typedef vector<vector<int> > VVI;
  141. typedef vector<VL> VVL;
  142.  
  143.  
  144. int ni()
  145. {
  146.     int _num; s(_num);
  147.     return _num;
  148. }
  149.  
  150. /*-------------------------Main code begins now ------------------------------*/
  151. int testnum;
  152. typedef vector<string> VS;
  153.  
  154. VS bestGrid, grid;
  155. int best;
  156. int N,M;
  157.  
  158. 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}}};
  159.  
  160. void preprocess()
  161. {
  162.  
  163. }
  164.  
  165. PII rotate(int x, int y, int dir)
  166. {
  167.     if(dir == 0) return PII(x,y);
  168.     if(dir == 1) return PII(-y, x);
  169.     if(dir == 2) return PII(-x, -y);
  170.     if(dir == 3) return PII(x,-y);
  171. }
  172.  
  173. bool isValid(int r, int c)
  174. {
  175.     return r >= 0 && c >=0 && r < N && c < M;
  176. }
  177.  
  178. int solve(int pos, int n, VS grid)
  179. {
  180.  
  181.     int x = pos / 3, y = pos % 3;
  182.    
  183.     if(pos == N * M)
  184.     {
  185.         if(n > best)
  186.         {
  187.             best = n;
  188.             bestGrid = VS(grid);
  189.             debug("Best", best, bestGrid);
  190.         }
  191.         return 0;
  192.     }
  193.  
  194.     int ans = 0;
  195.     VS orig = VS(grid);
  196.     for(int dir = 0; dir < 4; dir ++ )
  197.     {
  198.         grid = VS(orig);
  199.         bool ok = true;
  200.         for(int dx = -1; dx <= 1; dx++)
  201.             for(int dy = -1;dy <= 1; dy++)
  202.             {
  203.                 if(!isValid(x+dx, y+dy) || (T[dir][1+dx][1+dy] && grid[x+dx][y+dy] != '.'))
  204.                     ok = false;
  205.                
  206.                 else if(T[dir][1+dx][1+dy])
  207.                     grid[x+dx][y+dy] = (char)('A' + n);
  208.             }
  209.         if(ok)
  210.             ans = max(ans, 1 + solve(pos + 1, n+1,grid));
  211.     }
  212.     ans = max(ans, solve(pos+1, n, orig));
  213.     return ans;
  214. }
  215.    
  216.  
  217. void solve()
  218. {
  219.     best = 0;
  220.     VS grid;
  221.     grid.resize(N);
  222.  
  223.    
  224.     forall(i, 0, N)
  225.     {
  226.         string s = "";
  227.         forall(j, 0, M)
  228.             s += '.';
  229.         grid[i] = s;
  230.     }
  231.    
  232.     solve(0,0,grid);
  233.     cout << best << endl;
  234.     forall(i,0,N)
  235.         cout << bestGrid[i] << endl;
  236. }
  237.  
  238. bool input()
  239. {
  240.     s(N); s(M);
  241.     return true;
  242. }
  243.  
  244.  
  245. int main()
  246. {
  247.     preprocess();
  248.     int T = 1;
  249.     for(testnum=1;testnum<=T;testnum++)
  250.     {
  251.         if(!input()) break;
  252.         solve();
  253.     }
  254. }
Add Comment
Please, Sign In to add comment