搜索
DFS
最简单的DFS,排列数字
$N$个数字,全排列
#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int a[N];
bool st[N];
int n;
void _print(){
for(int i = 0;i<n;i++)printf("%d ",a[i]);
puts("");
}
void dfs(int u){
if(u==n){
_print();
return;
}
for(int i = 1;i<=n;i++){
if(!st[i]){
a[u] = i;
st[i] = true;
dfs(u+1);
st[i] = false;
}
}
}
int main(){
cin>>n;
dfs(0);
return 0;
}
N皇后
#include<bits/stdc++.h>
using namespace std;
const int N = 25;
char g[N][N];
bool m[N],a[N],b[N];
int n;
int p[N];
void _print(){
for(int i = 0;i<n;i++)cout<<g[i]<<endl;
puts("");
}
void dfs(int u){
if(u==n)return _print();
for(int i = 0;i<n;i++){
if(!m[i]&&!a[i+u]&&!b[i-u+n]){
g[u][i] = 'Q';
m[i] = a[u+i] = b[i-u+n] = true;
dfs(u+1);
m[i] = a[u+i] = b[i-u+n] = false;
g[u][i] = '.';
}
}
}
int main(){
cin>>n;
for(int i = 0;i<n;i++)
for(int j = 0;j<n;j++)g[i][j] = '.';
dfs(0);
return 0;
}
BFS
迷宫
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int g[N][N];
int d[N][N];
bool st[N][N];
int n,m;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
typedef pair<int,int> pii;
bool judge(int i,int j){
if(i>=n||i<0||j>=m||j<0)return false;
if(st[i][j])return false;
if(g[i][j] == 1)return false;
return true;
}
int main(){
cin>>n>>m;
for(int i = 0;i<n;i++)
for(int j = 0;j<m;j++)cin>>g[i][j];
queue<pii> q;
q.push({0,0});
d[0][0] = 0;
st[0][0] = true;
while(!q.empty()){
auto t = q.front();
q.pop();
for(int i = 0;i<4;i++){
int x = t.first+dx[i],y = t.second+dy[i];
if(judge(x,y)){
st[x][y] = true;
d[x][y] = d[t.first][t.second] + 1;
q.push({x,y});
}
}
}
cout<<d[n-1][m-1];
return 0;
}
持续更新…………