BFS

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

每次转换只能改变一个字母。转换过程中的中间单词必须是字典中的单词。

说明:

如果不存在这样的转换序列，返回 0。所有单词具有相同的长度。所有单词只由小写字母组成。字典中不存在重复的单词。你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例 1:

输入: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] 输出: 5 解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

得到的直接是最优解

int ladderLength(string beginWord, string endWord, vector<string>& wordList) { unordered_set<string> us(wordList.begin(),wordList.end()); unordered_set<string> visited; visited.insert(beginWord); queue<string> q; q.push(beginWord); int res=1; while(!q.empty()) { int size=q.size(); while(size-->0){ string cur = q.front(); q.pop(); if(cur == endWord) return res; for(int i = 0;i<cur.size();i++){ string tmp = cur; for(char c = 'a' ;c<='z';c++) { tmp[i] = c; if(!us.count(tmp) || visited.count(tmp)) continue; q.push(tmp); visited.insert(tmp); } } } res++; } return 0; }

完全平方数

class Solution { public: int numSquares(int n) { queue< pair<int,int> >q; q.push( make_pair(n,0) ); // n是给定的正整数，0是初始步数，为0. vector<bool> visited(n+1,false); //层序遍历减枝，图可能会反复遍历相同的节点。这里之前遍历过的，后面就不用遍历计算了。 visited[n] = true; while( !q.empty()){ int num = q.front().first; int step = q.front().second; q.pop(); for(int i = 1;i*i<=num;i++) { int a = num - i*i; if(a<0) break; if(a==0) return step+1;//当到达0节点，说明已经走完了。由于是层序的，第一个到达0节点就直接返回步数了。 if (!visited[a]) q.push( make_pair(a ,step + 1)); //记录到达当前节点，已经走了的步数。 visited[a] =true; } } return 0; } };

题目描述

假设一个探险家被困在了地底的迷宫之中，要从当前位置开始找到一条通往迷宫出口的路径。迷宫可以用一个二维矩阵组成，有的部分是墙，有的部分是路。迷宫之中有的路上还有门，每扇门都在迷宫的某个地方有与之匹配的钥匙，只有先拿到钥匙才能打开门。请设计一个算法，帮助探险家找到脱困的最短路径。如前所述，迷宫是通过一个二维矩阵表示的，每个元素的值的含义如下 0-墙，1-路，2-探险家的起始位置，3-迷宫的出口，大写字母-门，小写字母-对应大写字母所代表的门的钥匙

输入描述:

迷宫的地图，用二维矩阵表示。第一行是表示矩阵的行数和列数M和N 后面的M行是矩阵的数据，每一行对应与矩阵的一行（中间没有空格）。M和N都不超过100, 门不超过10扇。

输出描述:

路径的长度，是一个整数

示例1

输入

复制

5 5 02111 01a0A 01003 01001 01111

输出

复制

7 #include <iostream> #include <algorithm> #include <limits.h> #include <queue> using namespace std; int row, col; struct node{ int x,y,k,step; node(int x,int y,int k,int step):x(x),y(y),k(k),step(step){} }; int Next[4][2]={0,1,0,-1,1,0,-1,0}; int visit[105][105][1200] = {false}; int dfs(int startX, int startY, vector<vector<char>>& nums) { queue<node> Q; Q.push(node(startX,startY,0,0)); while(!Q.empty()) { node head = Q.front(); Q.pop(); if(nums[head.x][head.y] == '3') return head.step; for(int i=0;i<4;i++) { int new_x = head.x + Next[i][0]; int new_y = head.y + Next[i][1]; if(new_x < 0 || new_x>row-1 || new_y<0 || new_y>col-1 || nums[new_x][new_y]=='0') continue; int key=head.k; if(nums[new_x][new_y] >= 'a' && nums[new_x][new_y] <= 'z') key=key|(1<<(nums[new_x][new_y]-'a')); if(nums[new_x][new_y] >= 'A' && nums[new_x][new_y] <= 'Z' && (key & (1<<(nums[new_x][new_y]-'A')))==0) //door and no key continue; if(!visit[new_x][new_y][key]) { visit[new_x][new_y][key] = true; Q.push(node(new_x, new_y, key, head.step+1)); } } } return 0; } int main() { cin >> row >> col; vector<vector<char>> nums(row, vector<char>(col, 0)); for(int i = 0;i<row;i++) { for(int j=0; j< col;j++) { cin >> nums[i][j]; } } bool start_flag = false; for(int i=0;i<row;i++) { if(start_flag) break; for(int j=0;j<col;j++) { if(nums[i][j] == '2') { start_flag = true; visit[i][j][0] = true; cout << dfs(i, j, nums); break; } } } return 0; }