京东笔试求编程题答案

第一题dfs求连通加回溯遍历，只有5*5大小就是暴力的 第二题九个图拼一起，中间图起点dfs能到边界就是yes否则为no

没道理

参考一下这个网页https://www.cnblogs.com/butterflydew/p/9379915.html

第一题 82 #include<iostream> #include<vector> using namespace std; /* 3 3 2 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 2 2 2 */ struct pt { int col; int row; pt():col(0),row(0){} pt(int c, int r) :col(c), row(r) {} }; void dfs(int &sum, vector<vector<int>> nums, vector<vector<int>> &flag, int k, int i, int j) { if (flag[i][j] == -1 || nums[i][j] != k) return; sum++; flag[i][j] = -1; if (i - 1 >= 0) dfs(sum, nums, flag, k, i - 1, j); if (i + 1 < 5) dfs(sum, nums, flag, k, i + 1, j); if (j - 1 >= 0) dfs(sum, nums, flag, k, i, j - 1); if (j + 1 < 5) dfs(sum, nums, flag, k, i, j + 1); } vector<pt> solve(vector<vector<int>> nums) { vector<vector<int>> flag(5, vector<int>(5)); vector<pt> points; for (int k = 1; k < 4; k++) { for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { int sum = 0; dfs(sum,nums, flag, k, i, j); if (sum >= 3) { points.push_back(pt(j, i)); } } } } return points; } int func(vector<vector<int>> nums, pt point, int remain) { int sum = 0; dfs(sum, nums, nums, nums[point.row][point.col], point.row, point.col); remain -= sum; for (int i = 0; i < 4; i++) { for (int j = 0; j < 5; j++) { if (nums[i + 1][j] == -1 && nums[i][j] != -1) { swap(nums[i + 1][j], nums[i][j]); } } } vector<pt> points = solve(nums); if (points.size() < 1) return remain; int res = remain; for (int i = 0; i < points.size(); i++) { int re = func(nums, points[i], remain); res = res < re ? res : re; } return res; } int main() { vector<vector<int>> nums(5, vector<int>(5)); for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { cin >> nums[i][j]; } } vector<pt> points = solve(nums); int res = 25; for (int i = 0; i < points.size(); i++) { int re=func(nums, points[i], 25); res = res < re ? res : re; } cout << res << endl; return 0; }

第一题有啥思路没，每次只消最大的不行吧，比如一个1被2包围，2全部被1包围。

感觉时间不够调啊啊，第一题50%放弃，第二题本地ok,提交也是wrong answer ,求解😭😭😭😭

dfs，只消最大的会到55%，我就是只做到55%，时间来不及。

迷宫本地都能跑对，提交就是Wrong Answer不知道为什么。。