class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int row=board.size(),col=board[0].size();
int index=0,i=0,j=0;
if(word.size()>row*col) return 0;
//vector<vector<int>> visit[row][col];//標(biāo)記當(dāng)前位置有沒有被訪問過
vector<vector<int>> visit(row,vector<int>(col));
bool flag=1;
while(i<row&j<col)
{
cout<<"board[i][j]: "<<board[i][j]<<endl;
if(board[i][j]==word[index])
{
flag=1;
if(index==word.size()-1) return 1;
cout<<word[index]<<endl;
index++;
visit[i][j]=1;
if(i-1>=0&&board[i-1][j]==word[index]&&visit[i-1][j]!=1)
{
cout<<"上"<<endl;
i=i-1;
j=j;
}
else if(i+1<row&&board[i+1][j]==word[index]&&visit[i+1][j]!=1)
{
cout<<"下"<<endl;
i=i+1;
j=j;
}
else if(j-1>=0&&board[i][j-1]==word[index]&&visit[i][j-1]!=1)
{
cout<<"左"<<endl;
i=i;
j=j-1;
}
else if(j+1<col&&board[i][j+1]==word[index]&&visit[i][j+1]!=1)
{
cout<<"右"<<endl;
i=i;
j=j+1;
}
}
else
{
if(j==col-1&&i<row)//如果到了一行的最后面就調(diào)轉(zhuǎn)到下一行 大前提是找不到word[index]相等
{
cout<<"最末尾的 "<<board[i][j]<<endl;
i++;
j=0;
}
else j++;
}
}
return 0;
}
};
//寫的有點問題，暫時想不到怎么改，先放著，通過用例71/83 卡住的是abcd 但是改了又有問題
無語 看了 答案 都寫不對 在類成員里面定義了row和col 就不要重復(fù)定義了 不然不知道為什么就開始發(fā)瘋
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
rows=board.size();
cols=board[0].size();
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
if (dfs(board,word,i,j,0)) return true;
}
}
return false;
}
private:
int rows,cols;
bool dfs(vector<vector<char>>& board,string word,int i,int j,int k)
{
if(i>=rows||i<0||j>=cols||j<0||board[i][j]!=word[k]) return false;
if(k==word.size()-1) return true;
board[i][j]='\0';
bool res=dfs(board,word,i+1,j,k+1)||dfs(board,word,i-1,j,k+1)
||dfs(board,word,i,j+1,k+1)||dfs(board,word,i,j-1,k+1);
board[i][j]=word[k];
return res;
}
};
先貼出蠢貨寫出來的東西 審題也審不明白 機器人只能上下左右走 不能一行一行遍歷 菜鳥總是這樣 自己把自己搞破防
通過用列46/51
class Solution {
public:
int movingCount(int m, int n, int k) {
int index=0;
for(int i=0;i<m;i++)
{
if(add(i)>k) break;
for(int j=0;j<n;j++)
{
if(add(j)>k) break;
int sum=add(i)+add(j);
if(sum<=k)
{
index++;
cout<<sum<<endl;
}
}
}
return index;
}
private:
int add(int x)
{
int sum=0,num=0;
while(x)
{
num=x%10;
x=x/10;
sum+=num;
}
return sum;
}
};
問題出在哪里呢！?。?！ 就是比如【10，0】雖然數(shù)位之和等于1，但是無法通過【9，0】或者其他走過去，假設(shè)k=1的話，也就是他媽的他有障礙物啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
aaaa繼續(xù)做就是要判斷邊界條件啊啊啊啊啊啊啊啊啊啊啊啊就是判斷他是否能進入4個相鄰的格子
首先0，0必定可以嗷，check[0,0]置為1。0，0能走到0，1和1，0，那對于0，1和1，0兩個點來說，就是判斷他們的上面i-1和左邊j-1是否可以走，如果可以那就可以從左邊和上面分別走過來，能走到當(dāng)前這個點就置為1，然后左邊和上面能走的點都走了之后，還有兩個方向沒有判斷 ，再來判斷能不能從右邊(i+1)走到左邊,下面（i+1）走到上面，如果能走到當(dāng)前點，就置為1，最后有多少個1，就有多少個機器人能走的格子。
class Solution {
public:
int movingCount(int m, int n, int k) {
int index=0;
int check[m][n];
//不能直接寫check[m][n]也不能check[m][n]={0}，第一次無法保證元素全為0 ，第二個會報錯
memset(check,0,sizeof(check));
//memset進行內(nèi)存清零，可以將一塊內(nèi)存設(shè)置為指定的值
check[0][0]=1;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
int sum=add(i)+add(j);
if(sum<=k)
{
if(i-1>=0&&check[i-1][j]==1||j-1>=0&&check[i][j-1]==1) check[i][j]=1;
}
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
int sum=add(i)+add(j);
if(sum<=k)
{
if(i+1<m&&check[i+1][j]==1||j+1<n&&check[i][j+1]==1) check[i][j]=1;
}
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
int sum=add(i)+add(j);
if(check[i][j])
{
index++;
}
}
}
return index;
}
private:
int add(int x)
{
int sum=0,num=0;
while(x)
{
num=x%10;
x=x/10;
sum+=num;
}
return sum;
}
};
和上題目類似，屬于典型的搜索&回溯算法
先了解一下BFS模板
不需要當(dāng)前遍歷到哪一層，BFS模板
while queue 不空
cur=queue.front();
queue.pop();
for 結(jié)點 in cur的所有相鄰節(jié)點
if 該節(jié)點有效且沒被訪問過：
queue.push(該結(jié)點）
需要確定遍歷到哪一層，比如之前寫過一題打印二叉鏈表
level=0
while queue不空：
size=queue.size()
while(size--){
cur=queue.pop();
for 結(jié)點 in cur的所有相鄰結(jié)點：
if 該節(jié)點有效且未被訪問過：
queue.push(該節(jié)點）
}
level++;
直接使用模板
算了dfs
class Solution {
public:
int sum(int x){//計算數(shù)位和
int count = 0;
while(x){
count += x%10;
x /= 10;
}
return count;
}
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//左上右下
int res = 0;
int m , n , k;
vector<vector<bool>>st;
int movingCount(int _m, int _n, int _k) {
//m行n列
//不能進入行坐標(biāo)和列坐標(biāo)的"數(shù)位"之和大于k的格子
// i + j > k
m = _m, n = _n, k = _k;
vector<vector<bool>>_st(m,vector<bool>(n));//初始化
st = _st;
return dfs(0,0);
}
int dfs(int x, int y){
st[x][y]=true;
res++;
for(int i = 0 ;i < 4 ; i++){
int a = x+dx[i] , b = y + dy[i];
if(a >= 0 && a < m && b >= 0 && b < n && !st[a][b] && sum(a)+sum(b)<=k){
dfs(a,b);//那么我們就渲染一下
}
}
return res;
}
};
DFS解法文章來源：http://www.zghlxwxcb.cn/news/detail-609542.html
class Solution {
public:
int movingCount(int m, int n, int k) {
vector<vector<int>> check(m,vector<int>(n,0));//球球你了祖宗啊記住這個定義方式吧
dfs(check,m,n,k,0,0);
return result;
}
private:
int result=0;
int add(int x)
{
int sum=0,num=0;
while(x)
{
num=x%10;
x=x/10;
sum+=num;
}
return sum;
}
void dfs(vector<vector<int>> &check,int m, int n, int k,int x,int y)
{
int sum=add(x)+add(y);
if(x<0||x>=m||y<0||y>=n||check[x][y]==1||sum>k) return ;
result++;
check[x][y]=1;
dfs(check,m,n,k,x+1,y);
dfs(check,m,n,k,x,y+1);
}
};
BFS解法就見鬼去吧 不想寫隊列啊啊啊啊
文章來源地址http://www.zghlxwxcb.cn/news/detail-609542.html
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int target) {
if(!root) return result;
dfs(root,target);
return result;
}
private:
vector<vector<int>> result;
vector<int> subresult;
void dfs(TreeNode* root,int target)
{
if(!root) return ;
subresult.push_back(root->val);
target-=root->val;
if(root->left==nullptr&&root->right==nullptr&&target==0)
{
result.push_back(subresult);
}
dfs(root->left,target);
dfs(root->right,target);
subresult.pop_back();//回溯
}
};
到了這里，關(guān)于劍指offer12 矩陣中的路徑 13 機器人的運動范圍 34.二叉樹中和為某一值得路徑的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
