文章目录
- 1、太平洋大西洋水流问题
- 2、扫雷游戏
- 3、衣橱整理
1、太平洋大西洋水流问题
有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。
这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。
岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。
class Solution {
public:
int dx[4]={0,0,1,-1};
int dy[4]={-1,1,0,0};
int n,m;
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
n=heights.size();
m=heights[0].size();
vector<vector<int>> arr;
vector<vector<bool>> flag1(n,vector<bool>(m));
vector<vector<bool>> flag2(n,vector<bool>(m));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(i==0||j==0)
dfs(heights,i,j,flag1);
if(i==n-1||j==m-1)
dfs(heights,i,j,flag2);
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(flag1[i][j]&&flag2[i][j])
arr.push_back({i,j});
}
}
return arr;
}
void dfs(vector<vector<int>>& heights,int x,int y,vector<vector<bool>>& flag)
{
flag[x][y]=true;
for(int i=0;i<4;i++)
{
int x1=x+dx[i];
int y1=y+dy[i];
if(x1>=0&&y1>=0&&x1<n&&y1<m&&heights[x1][y1]>=heights[x][y]&&flag[x1][y1]==false)
dfs(heights,x1,y1,flag);
}
}
};
2、扫雷游戏
让我们一起来玩扫雷游戏！
给你一个大小为 m x n 二维字符矩阵 board ，表示扫雷游戏的盘面，其中：
‘M’ 代表一个 未挖出的 地雷，
‘E’ 代表一个 未挖出的 空方块，
‘B’ 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的 已挖出的 空白方块，
数字（‘1’ 到 ‘8’）表示有多少地雷与这块 已挖出的 方块相邻，
‘X’ 则表示一个 已挖出的 地雷。
给你一个整数数组 click ，其中 click = [clickr, clickc] 表示在所有 未挖出的 方块（‘M’ 或者 ‘E’）中的下一个点击位置（clickr 是行下标，clickc 是列下标）。
根据以下规则，返回相应位置被点击后对应的盘面：
如果一个地雷（‘M’）被挖出，游戏就结束了- 把它改为 ‘X’ 。
如果一个 没有相邻地雷 的空方块（‘E’）被挖出，修改它为（‘B’），并且所有和其相邻的 未挖出 方块都应该被递归地揭露。
如果一个 至少与一个地雷相邻 的空方块（‘E’）被挖出，修改它为数字（‘1’ 到 ‘8’ ），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回盘面。
class Solution {
public:
int n,m;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
n=board.size();
m=board[0].size();
if(board[click[0]][click[1]]=='M')
{
board[click[0]][click[1]]='X';
return board;
}
dfs(board,click[0],click[1]);
return board;
}
void dfs(vector<vector<char>>& board,int x,int y)
{
int count=0;
for(int i=0;i<8;i++)
{
int x1=x+dx[i];
int y1=y+dy[i];
if(x1>=0&&y1>=0&&x1<n&&y1<m&&board[x1][y1]=='M')
count++;
}
if(count)
{
board[x][y]=count+'0';
return ;
}
else
{
board[x][y]='B';
for(int i=0;i<8;i++)
{
int x1=x+dx[i];
int y1=y+dy[i];
if(x1>=0&&y1>=0&&x1<n&&y1<m&&board[x1][y1]=='E')
dfs(board,x1,y1);
}
}
}
};
3、衣橱整理
家居整理师将待整理衣橱划分为 m x n 的二维矩阵 grid，其中 grid[i][j] 代表一个需要整理的格子。整理师自 grid[0][0] 开始 逐行逐列 地整理每个格子。
整理规则为：在整理过程中，可以选择 向右移动一格 或 向下移动一格，但不能移动到衣柜之外。同时，不需要整理 digit(i) + digit(j) > cnt 的格子，其中 digit(x) 表示数字 x 的各数位之和。
请返回整理师 总共需要整理多少个格子。
class Solution {
public://注意审题
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int n, m, cnt;
int count = 0;
int wardrobeFinishing(int n1, int m1, int cnt1) {
n = n1, m = m1, cnt = cnt1;
vector<vector<bool>> dummy(n, vector<bool>(m));
dfs(dummy, 0, 0);
return count;
}
void dfs(vector<vector<bool>>& dummy, int x, int y) {
count++;
dummy[x][y] = true;
for (int i = 0; i < 4; i++) {
int x1 = x + dx[i];
int y1 = y + dy[i];
if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m &&
dummy[x1][y1] == false&&check(x1,y1)) {
dfs(dummy, x1, y1);
}
}
}
bool check(int i,int j)
{
int tmp=0;
while(i)
{
tmp+=i%10;
i/=10;
}
while(j)
{
tmp+=j%10;
j/=10;
}
return tmp<=cnt;
}
};
