本文主要是介绍723. Candy Crush,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
https://leetcode.com/problems/candy-crush/description/
题目大意:就是消消乐,横竖数字相同且连起来大于3的消掉.
解题思路:暴力法,遍历每个位置,然后检查是否有横竖连续大于3的,有就将该位置记录在to_crash中.然后对 to_crash中的点进行处理,直到to_Crash为空.画图模拟比较好理解.
代码:
class Solution {
public:vector<vector<int>> candyCrush(vector<vector<int>>& board) {int m = board.size();int n = board[0].size(); while (true) {vector<pair<int, int>> to_crash;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (board[i][j]) { //为了减小计算量,元素为0的略过int i1 = i, i0 = i, j1 = j, j0 = j; // i1,i0,j1,j0分别为向下,向上,向右,向左的检测//对每个点(i,j),以其为中心,向上下或左右方向扩展,看是否有连续while (i1 < m && i1 < i+3 && board[i1][j] == board[i][j]) i1++;while (i0 >= 0 && i0 > i-3 && board[i0][j] == board[i][j]) i0--;while (j1 < n && j1 < j+3 && board[i][j1] == board[i][j]) j1++;while (j0 >= 0 && j0 > j-3 && board[i][j0] == board[i][j]) j0--;if (i1-i0 > 3 || j1-j0 > 3) to_crash.push_back({i,j}); //上下或左右连续元素超过3,即符合}}}if (to_crash.empty()) break;for (auto t : to_crash) board[t.first][t.second] = 0; //重点:将所有标记位置置0for (int j = 0; j < n; j++) { //由于是自上往下消除,因此外层对j(纵坐标)循环 int t = m-1; //t用于记录新board的横坐标for (int i = m-1; i >= 0; i--) { //从下往上,非0元素参与交换,每次交换后t上移if (board[i][j]) swap(board[i][j], board[t--][j]);}}}return board;}
};
这篇关于723. Candy Crush的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!