Bfs的板子
#include <bits/stdc++.h>
using namespace std;
int n,m;int visited[100][100];int g[100][100];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
void bfs(int x,int y)
{queue<pair<int,int> >p;//就是逗号 p.push({x,y});//多个的结构体打包 while(!p.empty()){auto it=p.front();p.pop();int cx=it.first;int cy=it.second;//这里加具体题目的终点判断返回值 for(int i=0;i<4;i++)//超级可乐没有for的 {int nx=x+dx[i];int ny=y+dy[i];//这里最全 剪枝 曼哈顿不用 if(nx<0||nx>=n||ny<0||ny>=m) continue;if(g[nx][ny]) continue;//合并成地图的也行 if(visited[nx][ny]) continue;visited[nx][ny]=1;p.push({nx,ny});}}
}
int main()
{cin>>n>>m;memset(visited,0,sizeof(visited));//多组数据的清空 for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>g[i][j];}}visited[0][0]=1;bfs(0,0);
}
Dfs的板子和回溯
#include <bits/stdc++.h>
using namespace std;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int n,m;
int visited[100][100];int g[100][100];
void dfs(int x,int y)
{for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];//题目的目标在这里 if(nx<0||nx>=n||ny<0||ny>=m) continue;if(visited[nx][ny]) continue;if(g[nx][ny]) continue;//剪枝 曼是T-nt-abs(sx-nx)-abs(sy-ny) <0||奇数跳过 visited[nx][ny]=1;dfs(nx,ny);//你就用全局变量吧老是忘记返回值 visited[nx][ny]=0;//退出房间回溯吧 }
}
int main()
{cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>g[i][j];}}//这里剪枝 count和曼 visited[0][0]=1;//一万个牢记 dfs(0,0);
}