文章目录
蛇梯棋
N x N 的棋盘 board 上，按从 1 到 N*N 的数字给方格编号，编号 从左下角开始，每一行交替方向。
例如，一块 6 x 6 大小的棋盘，编号如下：r 行 c 列的棋盘，按前述方法编号，棋盘格中可能存在 “蛇” 或 “*”；如果 board[r][c] != -1，那个蛇或*的目的地将会是 board[r][c]。玩家从棋盘上的方格 1 （总是在最后一行、第一列）开始出发。每一回合，玩家需要从当前方格 x 开始出发，按下述要求前进：选定目标方格：选择从编号 x+1，x+2，x+3，x+4，x+5，或者 x+6 的方格中选出一个目标方格 s ，目标方
题解：
1.将二维数组按照Z字形遍历转成一维数组
2.利用队列进行bfs搜索，注意用哈希表记录访问过的节点
3.当走到一个点时，先判断arr[index]是否为-1，不为-1则跳到对应的点去 -> index = arr[index] -1 ; -1是因为数组中保存的是对应的位置而不是下标
class Solution {
public:
int snakesAndLadders(vector<vector<int>>& board) {
if(board.size()<2)//只有一个点
return 0;
//先将二维数组扁平化为一维数组
vector<int>arr;
int flag=1;
for(int i=board.size()-1;i>=0;i--)
{
if(flag==-1)
{
for(int j=board.size()-1;j>=0;j--)
arr.push_back(board[i][j]);
}
else
{
for(int j=0;j<board.size();j++)
arr.push_back(board[i][j]);
}
flag*=-1;
}
queue<int>qe;
unordered_set<int> record;//标记出现过的点
qe.push(0);
record.insert(0);
int count=0;//记录步伐
int end=board.size()*board.size();//终点
int size=1;//记录当前层元素个数
while(!qe.empty())
{
int index=qe.front();
qe.pop();
size--;
for(int i=1;i<=6;i++)
{
int next=index + i;
if(arr[next]!=-1)
next=arr[next]-1;
if(record.find(next)==record.end())//没有出现过
{
if(next==end-1)
return count+1;
record.insert(next);
qe.push(next);
}
}
if(size==0)
{
count++;
size=qe.size();
}
}
return -1;
}
};
单词接龙
题解：
1.bfs常规套路 -> 准备队列，走的步伐数，记录走过节点的哈希表(存储走过的节点和当前节点对应的步伐数)
2.由于数据量过大，因此采用双端队列-> 分别从开始和末尾出发
3.将字典的单词加入哈希表中方便查找
4.变化一个单词 -> 构建一个函数，进行遍历，每个位置的单词从 a~z进行变化即可
5.当一边中出现的单词，在另外一边出现过了，则说明找到了最短路径 -> 两个路径相加则表示总共走过了多少步，需要注意的是返回的结果需要+1，因为最后一步是没有记录的
6.需要注意的是，最后一个单词应该在字典表中 && 只有两个单词时，最后一个单词先走，会得不到结果，因为第一个单词可能不在单词表中
class Solution {
public:
void Add(queue<string>&qe,string &str,unordered_map<string,int>&record,int &count,
unordered_set<string> &list)//下一步可以变化的单词加入队列中
{
for(int i=0;i<str.size();i++)//每次变化一个字符
{
for(int j='a';j<='z';j++)//每种字符25种变化
{
if(j==str[i])//没有变化
continue;
char copy=str[i];
str[i]=j;
if(list.find(str)!=list.end()&&record.find(str)==record.end())//在字典中&&没有出现过
{
qe.push(str);
record[str]=count+1;
}
str[i]=copy;//恢复
}
}
}
void bfs(queue<string>&qe,unordered_map<string,int>&record1,unordered_map<string,int>&record2,int &ret,int &count,unordered_set<string> &list)
{
int size=qe.size();
while(size--)
{
string str=qe.front();
qe.pop();
if(record2.find(str)!=record2.end())//在另外一边出现过了
{
ret=count+record2[str];
return;
}
//添加下一个字符
Add(qe,str,record1,count,list);
}
count ++;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
if(beginWord==endWord)//开始就相等
return 0;
unordered_set<string> list;
for(auto&e:wordList)
{
list.insert(e);//将字符添加到哈希字典之中
}
if(list.find(endWord)==list.end())
return 0;//尾不在字典之中
unordered_map<string,int> record1;
unordered_map<string,int> record2;
int count1=0;
int count2=0;
queue<string>qe1;
queue<string>qe2;
//加入字符
qe1.push(beginWord);
qe2.push(endWord);
record1[beginWord]=0;
record2[endWord]=0;
int ret=0;
while(!qe1.empty()&&!qe2.empty())
{
if(qe1.size()<=qe2.size())
bfs(qe1,record1,record2,ret,count1,list);
else
bfs(qe2,record2,record1,ret,count2,list);
if(ret!=0)
return ret+1;
}
return 0;
}
};
青蛙过河
一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。
题解：
1.用一个哈希表记录所有的石块
2.unordered_map<int,vector> 记录跳到一个石块时，上一步的跳跃的距离 -> 去重可以跳到同一个石块，但是上一步不能是同一个石块
3.一个队列 queue<vector> qe，记录当前所处的位置，和上一跳的距离
4.进行位置更新，看下一步到达的地点，是否出现过，如果没有出现过，则添加到队列之中
class Solution {
public:
bool find(unordered_map<int,vector<int>>&record,int n,int k)
{
vector<int> ve=record[n];
for(int i=0;i<ve.size();i++)
{
if(ve[i]==k)
return false;
}
record[n].push_back(k);
return true;
}
bool canCross(vector<int>& stones) {
//注意点：跳到同样的位置，但是上一步的跳跃距离不一样
vector<int> arr(2,0);//记录当前的位置，和上一次跳的步伐
unordered_set<int> st;//记录石头编号
for(auto&e:stones)
{
st.insert(e);
}
if(st.find(stones[0]+1)==st.end())//第一步就，跳到了水中
return false;
if(stones.size()==2)//只有两块石头,就到达了
return true;
arr[0]=stones[0]+1;//当前位置
arr[1]=1;//上一跳的距离
queue<vector<int>> qe;
unordered_map<int,vector<int>> record;//记录到达的石块
qe.push(arr);
record[arr[0]].push_back(1);
while(!qe.empty())
{
vector<int> ve=qe.front();
qe.pop();
if(ve[0]==*(--stones.end()))//跳到了最后一个位置
return true;
int k=ve[1];//上一跳的距离
int jump1=ve[0]+k-1;
int jump2=ve[0]+k;
int jump3=ve[0]+k+1;
if(jump1>0&&st.find(jump1)!=st.end()&&find(record,jump2,k-1))
{
vector<int> temp;
temp.push_back(jump1);
temp.push_back(k-1);
qe.push(temp);
}
if(jump2>0&&st.find(jump2)!=st.end()&&find(record,jump2,k))
{
vector<int> temp;
temp.push_back(jump2);
temp.push_back(k);
qe.push(temp);
}
if(jump3>0&&st.find(jump3)!=st.end()&&find(record,jump2,k+1))
{
vector<int> temp;
temp.push_back(jump3);
temp.push_back(k+1);
qe.push(temp);
}
}
return false;
}
};
以上就是本文的全部内容，希望对大家的学习有所帮助