图中点的层次（宽搜框架）
#include
#include
#include
using namespace std;
const int N = 10010;
int n , m;
int h [N],e[N],ne[N],idx;
int d[N],q[N];
void add(int a ,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs()
{
int hh=0,tt = 0;
q[0]=1;
memset(d,-1,sizeof d);
d[1]=0;
while(hh<=tt)
{
int t=q[hh++];
for (int i =h[t];i!=-1;i=ne[i])
{
int j =e[i];
if(d[j]==-1)
{
d[j]=d[t]+1;
q[++tt] =j;
}
}
}
return d[n];
}
int main()
{
cin >>n >> m;
memset(h,-1,sizeof h );
for (int i =0;i {
int a,b;
cin >> a >> b;
add(a,b);
}
cout << bfs() << endl;
return 0 ;
}
#include
#include
#include
using namespace std;
const int N = 10010;
int n , m;
int h [N],e[N],ne[N],idx;
int d[N],q[N];
void add(int a ,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs()
{
int hh=0,tt = 0;
q[0]=1;
memset(d,-1,sizeof d);
d[1]=0;
while(hh<=tt)
{
int t=q[hh++];
for (int i =h[t];i!=-1;i=ne[i])
{
int j =e[i];
if(d[j]==-1)
{
d[j]=d[t]+1;
q[++tt] =j;
}
}
}
return d[n];
}
int main()
{
cin >>n >> m;
memset(h,-1,sizeof h );
for (int i =0;i
int a,b;
cin >> a >> b;
add(a,b);
}
cout << bfs() << endl;
return 0 ;
}
八皇后 （dfs）
#include
using namespace std;
const int N =20;
int n;
char g[N][N];
bool col[N],dg[N],udg[N]; //判断直边，两个斜边是否被占用
void dfs(int u)
{
if(u==n)//到最后一行
{
for (int i=0;i puts("");
return;
}
for(int i =0;i if(!col[i] && !dg[u+i] && !udg[n-u+i]) //类似于截距
{
g[u][i]='Q';
col[i]=dg[u+i]=udg[n-u+i]=true;
dfs(u+1);
col[i] = dg[u+i] = udg[n-u+i]=false;
g[u][i]='.';
}
}
int main()
{
cin >> n;
for (int i =0;i for (int j=0;jg[i][j]='.';
dfs(0);
return 0;
}
#include
using namespace std;
const int N =20;
int n;
char g[N][N];
bool col[N],dg[N],udg[N]; //判断直边，两个斜边是否被占用
void dfs(int u)
{
if(u==n)//到最后一行
{
for (int i=0;i
return;
}
for(int i =0;i
{
g[u][i]='Q';
col[i]=dg[u+i]=udg[n-u+i]=true;
dfs(u+1);
col[i] = dg[u+i] = udg[n-u+i]=false;
g[u][i]='.';
}
}
int main()
{
cin >> n;
for (int i =0;i
dfs(0);
return 0;
}
DFS模板
#include
using namespace std;
const int N =10;
int n;
int path[N];
bool st[N]; //判断是否被使用过
void dfs(int u)
{
if(u==n)//遍历到最后一层就直接返回
{
for(int i =0;i puts("");
return;
}
for(int i =1;i<=n;i++)
if(!st[i])
{
path[u]=i;
st[i]=true;
dfs(u+1);
st[i]=false; //恢复现场
}
}
int main()
{
cin >> n;
dfs(0);
return 0;
}
#include
using namespace std;
const int N =10;
int n;
int path[N];
bool st[N]; //判断是否被使用过
void dfs(int u)
{
if(u==n)//遍历到最后一层就直接返回
{
for(int i =0;i
return;
}
for(int i =1;i<=n;i++)
if(!st[i])
{
path[u]=i;
st[i]=true;
dfs(u+1);
st[i]=false; //恢复现场
}
}
int main()
{
cin >> n;
dfs(0);
return 0;
}
✋热门推荐