1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 21;
  4. int topCount[N];
  5. int leftCount[N];
  6. bool vis[N][N] = {false};
  7. int curTop[N] = {0};
  8. int curLeft[N] = {0};
  9. bool found = false;
  10. class Node{
  11. public:
  12. int x, y;
  13. Node(int i, int j) {
  14. x = i;
  15. y = j;
  16. }
  17. };
  18. int dx[4] = {1, 0, -1, 0};
  19. int dy[4] = {0, 1, 0, -1};
  20. bool check(int n) {
  21. for (int i = 0; i < n; i++) {
  22. if (topCount[i] != curTop[i] || leftCount[i] != curLeft[i]) {
  23. return false;
  24. }
  25. }
  26. return true;
  27. }
  28. void dfs(int x, int y, int n, vector<Node> &buf)
  29. {
  30. if (curLeft[x] == leftCount[x] || curTop[y] == topCount[y]) {
  31. return;
  32. }
  33. curLeft[x]++;
  34. curTop[y]++;
  35. buf.push_back(Node(x, y));
  36. vis[x][y] = true;
  37. if (x == n-1 && y == n-1) {
  38. if (check(n)) {
  39. found = true;
  40. for (int i = 0; i < buf.size(); i++) {
  41. cout << n * buf[i].x + buf[i].y << " ";
  42. }
  43. }
  44. } else {
  45. for (int i = 0; i < 4; i++) {
  46. if (found) {
  47. return;
  48. }
  49. int tx = x + dx[i];
  50. int ty = y + dy[i];
  51. if (tx < 0 || tx >= n || ty < 0 || ty >= n || vis[tx][ty]) {
  52. continue;
  53. }
  54. dfs(tx, ty, n, buf);
  55. }
  56. }
  57. buf.pop_back();
  58. curTop[y]--;
  59. curLeft[x]--;
  60. vis[x][y] = false;
  61. }
  62. int main()
  63. {
  64. int n;
  65. cin >> n;
  66. for (int i = 0; i < n; i++) {
  67. cin >> topCount[i];
  68. }
  69. for (int i = 0; i < n; i++) {
  70. cin >> leftCount[i];
  71. }
  72. vector<Node> buf;
  73. dfs(0, 0, n, buf);
  74. return 0;
  75. }
点赞(1)
 

10 分

1 人评分

 

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论