fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. #pragma warning (disable: 4996)
  6.  
  7. int a[19][19], H, W, maxn = 0;
  8.  
  9. bool check(int px, int py) {
  10. 	int dx[9] = { -1, -1, -1, 0, 1, 1, 1, 0, 0 };
  11. 	int dy[9] = { -1, 0, 1, 1, 1, 0, -1, -1, 0 };
  12. 	for (int i = 0; i < 9; i++) {
  13. 		int ex = px + dx[i], ey = py + dy[i];
  14. 		if (ex < 0 || ey < 0 || ex >= H || ey >= W) continue;
  15. 		if (a[ex][ey] == 1) return false;
  16. 	}
  17. 	return true;
  18. }
  19.  
  20. void dfs(int dep, pair<int, int> L) {
  21. 	maxn = max(maxn, dep);
  22.  
  23. 	for (int i = 0; i < H - 1; i++) {
  24. 		for (int j = 0; j < W; j++) {
  25. 			if (make_pair(i, j) <= L) continue;
  26. 			bool I1 = check(i, j);
  27. 			bool I2 = check(i + 1, j);
  28.  
  29. 			if (I1 == true && I2 == true) {
  30. 				a[i][j] = 1; a[i + 1][j] = 1;
  31. 				dfs(dep + 1, make_pair(i, j));
  32. 				a[i][j] = 0; a[i + 1][j] = 0;
  33. 			}
  34. 		}
  35. 	}
  36.  
  37. 	for (int i = 0; i < H; i++) {
  38. 		for (int j = 0; j < W - 1; j++) {
  39. 			if (make_pair(i, j) <= L) continue;
  40. 			bool I1 = check(i, j);
  41. 			bool I2 = check(i, j + 1);
  42.  
  43. 			if (I1 == true && I2 == true) {
  44. 				a[i][j] = 1; a[i][j + 1] = 1;
  45. 				dfs(dep + 1, make_pair(i, j));
  46. 				a[i][j] = 0; a[i][j + 1] = 0;
  47. 			}
  48. 		}
  49. 	}
  50. }
  51.  
  52. int main() {
  53. 	for (int i = 1; i <= 15; i++) {
  54. 		for (int j = 1; j <= 15; j++) {
  55. 			if (i*j > 44) continue;
  56. 			H = i; W = j; maxn = 0;
  57. 			dfs(0, make_pair(-1, -1));
  58. 			printf("% 3d", maxn);
  59. 		}
  60. 		cout << endl;
  61. 	}
  62. 	return 0;
  63. }
Success #stdin #stdout 2.53s 15232KB
comments (?)
stdin 
Standard input is empty
stdout 
  0  1  1  1  2  2  2  3  3  3  4  4  4  5  5
  1  1  2  2  3  3  4  4  5  5  6  6  7  7  8
  1  2  2  3  4  4  5  6  6  7  8  8  9 10
  1  2  3  4  5  5  6  7  8  9 10
  2  3  4  5  6  7  8  9
  2  3  4  5  7  8  9
  2  4  5  6  8  9
  3  4  6  7  9
  3  5  6  8
  3  5  7  9
  4  6  8 10
  4  6  8
  4  7  9
  5  7 10
  5  8
https://ideone.com/Vq33ab
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!