算法与分析课程_回溯算法_拼题网_习题5_666_C++

5 666
小明有一张m*n的好习惯记录卡，记录每一天的好习惯目标达成度（数字0-9表示）。某天目标完成达成，就在当天的格子里写上数字6，目标没有完全达成就写上一个小于6的数字（0-5），目标超额完成就写上一个大于6的数字（7-9）。记录卡上如果能找到一条长度为3的路径并且路径上的三个数字都大于等于6（这里的路径是指从某个格子出发，可以向左、右、上、下格子移动，并且不能重复经过一个格子），则小明就能得到一个“666”奖励。
请你帮小明统计下他总共能得到多少“666”奖励。

输入格式:
输入第一行给出两个正整数m,n(1=

输出格式:
先输出m行，每行包括n个整数，代表从当前格子出发得到的“666”奖励个数，中间用空格分割，最后一个数字后面不带空格。然后再在下一行输出得到的“666”奖励总数。

输入样例:

3 3
6 6 7
3 8 3
7 9 5

输出样例:

2 1 2
0 3 0
1 1 0
10

代码:
直接递归+穷举求解
忽略回溯函数!!!

#include
#include
using namespace std;
class Solution {
public:int pathCheck(int len, vector<vector<vector<int>>>& nums);//(长度,数组,最初的行坐标,最初的列坐标,下一个判断点行坐标,下一个判断点列坐标,当前组成的路径长度,方案总个数,行走方向)void backTrack(int len, vector<vector<vector<int>>>& nums, int firstRow, int firstCol, int nextRow, int nextCol, int pathLength, int& count,int flag);
};
int Solution::pathCheck(int len, vector<vector<vector<int>>>& nums) {int ret = 0;for (int row = 0; row < nums.size(); row++) {for (int col = 0; col < nums.at(0).size(); col++) {backTrack(len, nums, row, col, row, col, 1, ret,0);cout <<nums.at(row).at(col).at(1);if (col != nums.at(0).size() - 1)cout << " ";}cout << endl;}return ret;
}
void Solution::backTrack(int len, vector<vector<vector<int>>>& nums, int firstRow, int firstCol,int nextRow,int nextCol,int pathLength,int& count,int flag) {if (nextRow < 0 || nextCol < 0)return;if (nextRow == nums.size()|| nextCol ==nums[0].size())return;if (nums.at(nextRow).at(nextCol).at(0) < 6)return;if (pathLength == len) {nums.at(firstRow).at(firstCol).at(1)++;count++;return;}if (flag == 1) {backTrack(len, nums, firstRow, firstCol, nextRow - 1, nextCol, pathLength + 1, count, 1);//向上backTrack(len, nums, firstRow, firstCol, nextRow, nextCol - 1, pathLength + 1, count, 3);//向左backTrack(len, nums, firstRow, firstCol, nextRow, nextCol+1, pathLength + 1, count, 4);//向右}else if (flag == 2) {backTrack(len, nums, firstRow, firstCol, nextRow + 1, nextCol, pathLength + 1, count, 2);//向下backTrack(len, nums, firstRow, firstCol, nextRow, nextCol - 1, pathLength + 1, count, 3);//向左backTrack(len, nums, firstRow, firstCol, nextRow, nextCol+1, pathLength + 1, count, 4);//向右}else if (flag == 3) {backTrack(len, nums, firstRow, firstCol, nextRow - 1, nextCol, pathLength + 1, count, 1);//向上backTrack(len, nums, firstRow, firstCol, nextRow + 1, nextCol, pathLength + 1, count, 2);//向下backTrack(len, nums, firstRow, firstCol, nextRow, nextCol - 1, pathLength + 1, count, 3);//向左}else if(flag==4){backTrack(len, nums, firstRow, firstCol, nextRow, nextCol+1, pathLength + 1, count, 4);//向右backTrack(len, nums, firstRow, firstCol, nextRow + 1, nextCol, pathLength + 1, count, 2);//向下backTrack(len, nums, firstRow, firstCol, nextRow - 1, nextCol, pathLength + 1, count, 1);//向上}else {backTrack(len, nums, firstRow, firstCol, nextRow, nextCol - 1, pathLength + 1, count, 3);//向左backTrack(len, nums, firstRow, firstCol, nextRow, nextCol + 1, pathLength + 1, count, 4);//向右backTrack(len, nums, firstRow, firstCol, nextRow + 1, nextCol, pathLength + 1, count, 2);//向下backTrack(len, nums, firstRow, firstCol, nextRow - 1, nextCol, pathLength + 1, count, 1);//向上}
}
int main() {int m, n;cin >> m >> n;vector<vector<vector<int>>> nums(m,vector<vector<int>>(n, vector<int>(2,0)));for (int i = 0; i < m; i++) {for (int k = 0; k < n; k++) {cin >> nums.at(i).at(k).at(0);}}Solution A;cout<<A.pathCheck(3, nums)<<endl;system("pause");return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！