BFS
最短步数问题
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 50;
char g[N][N],d[N][N];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int n,m;
int bfs(int x,int y){
queue<pair<int,int> > q;
q.push({x,y});
memset(d,-1,sizeof(d));
d[x][y] = 1;
while(!q.empty()){
auto t = q.front();
q.pop();
for(int i = 0; i < 4; i++){
int sx = t.first+dx[i];
int sy = t.second+dy[i];
if(sx >= 0 && sy >= 0 && sx < n && sy < m && d[sx][sy] == -1 && g[sx][sy] == '.'){
q.push({sx,sy});
d[sx][sy] = d[t.first][t.second]+1;
}
}
}
return d[n-1][m-1];
}
int main(){
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> g[i];
cout << bfs(0,0) << endl;
return 0;
}
洪水填充：连通块问题
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 120;
char g[N][N];
bool d[N][N];
int n,m;
int dx[8] = {-1,-1,-1,0,1,1,1,0};
int dy[8] = {-1,0,1,1,1,0,-1,-1};
int bfs(int sx,int sy){
queue<pair<int,int>> q;
q.push({sx,sy});
g[sx][sy] = '.';
while(!q.empty()){
auto h = q.front();
q.pop();
for(int i = 0; i < 8; i++){
int x = h.first + dx[i];
int y = h.second + dy[i];
if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 'W'){
q.push({x,y});
g[x][y] = '.';
}
}
}
}
int main(){
cin >> n >> m;
int ans = 0;
for(int i = 0; i < n; i++) cin >> g[i];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(g[i][j] == 'W'){
bfs(i,j);
ans++;
}
}
}
cout << ans << endl;
return 0;
}
最短路：输出路径
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 50;
int a[5][5];
bool st[N][N];
typedef pair<int,int> PII;
PII h[25];
PII Prev[5][5];
int hh,tt;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int bfs(int sx,int sy){
hh = 0;
tt = -1;
h[++tt] = {sx,sy};
memset(Prev,-1,sizeof Prev);
while(hh <= tt){
PII t = h[hh++];
for(int i = 0; i < 4; i++){
int x = t.first + dx[i];
int y = t.second + dy[i];
if(x >= 0 && x < 5 && y >= 0 && y < 5 && a[x][y] == 0 && st[x][y] == false){
h[++tt] = {x,y};
Prev[x][y] = t;
st[x][y] = 1;
}
}
}
}
int main(){
for(int i = 0; i < 5; i++){
for(int j = 0; j < 5; j++){
cin >> a[i][j];
}
}
bfs(4,4);
PII end(0,0);
while(true){
cout << "(" << end.first << ", " << end.second << ")" << endl;
if(end.first == 4 && end.second == 4) break;
end = Prev[end.first][end.second];
}
}
DFS
组合型枚举：无限制数量
#include<iostream>
using namespace std;
int a[10000];
int n,sum;
void dfs(int t,int idx,int s){
if(s == n){
cout << n << "=" << a[0];
for(int i = 1; i < t; i++){
cout << "+" << a[i];
}
cout << endl;
sum++;
return;
}
for(int i = idx; i < n; i++){
if(i <= n-s+1){
a[t] = i;
dfs(t+1,i,s+i);
}
}
}
int main(){
cin >> n;
dfs(0,1,0);
return 0;
}
组合型枚举：有数量限制
#include<bits/stdc++.h>
using namespace std;
int a[1000];
int n,k;
void func(int m,int idx){
if(m == k){
for(int i = 0; i < m; i++) printf("%3d",a[i]);
cout << endl;
}
for(int i = idx+1; i <= n; i++){ //idx为我上次找到元素的位置从后面继续找
a[m] = i;
func(m+1,i); //m+1搭配方案里的元素+1，idx=i为我现在看到的元素位置
}
}
int main(){
cin >> n >> k;
func(0,0);
return 0;
}
全排列
#include<iostream>
using namespace std;
int n;
int a[10000],v[1000000];
void dfs(int x){
if(x == n){
for(int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
}
for(int i = 1; i <= n; i++){
if(v[i] == 0){
a[x] = i;
v[i] = 1;
dfs(x+1);
v[i] = 0;
}
}
}
int main(){
cin >> n;
dfs(0);
}
八皇后
#include<iostream>
using namespace std;
const int N = 1001;
char g[N][N];
bool col[N],dg[N],udg[N];
int n,cnt;
void dfs(int u){
if(u == n){
cnt++;
cout << "No. " << cnt << endl;
for(int j = 0; j < n; j++){
for(int i = 0; i < n; i++){
if(g[j][i] == 'Q') cout << 1 << " ";
else cout << 0 << " ";
}
cout << endl;
}
return ;
}
for(int i = 0; i < n; 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(){
n = 8;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
g[i][j] = '.';
}
}
dfs(0);
return 0;
}
图论：
存储与遍历
vectoer
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e3+10;
vector<vector<int> > g(N);
bool st[N];
int n,m;
void bfs(int x){
queue<int> q;
q.push(x);
st[x] = 1;
cout << x << " ";
while(!q.empty()){
int t = q.front();
q.pop();
for(int i = 0; i < g[t].size(); i++){
if(!st[g[t][i]]){
q.push(g[t][i]);
st[g[t][i]] = 1;
cout << g[t][i] << " ";
}
}
}
}
void dfs(int x){
st[x] = 1;
cout << x << " ";
for(int i = 0; i < g[x].size(); i++){
if(!st[g[x][i]]) dfs(g[x][i]);
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
int a,b; cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
for(int i = 1; i <= n; i++){
for(int j = 0; j < g[i].size(); j++){
cout << i << "---->" << g[i][j] << endl;
}
}
bfs(1);
cout << endl;
memset(st,0,sizeof(st));
dfs(1);
return 0;
}
/*
9 8
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
*/
临接矩阵-数组
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e3+10;
int n,m;
int g[N][N];
int v[N];
void bfs(int x){
queue<int> q;
q.push(x);
v[x] = 1;
cout << x << " ";
while(!q.empty()){
int t = q.front();
q.pop();
for(int i = 1; i <= n; i++){
if(g[t][i] && !v[i]){
q.push(i);
cout << i << " ";
v[i] = 1;
}
}
}
}
void dfs(int x){
v[x] = 1;
cout << x << " ";
for(int i = 1; i <= n; i++){
if(g[x][i] && !v[i]) dfs(i);
}
}
int main(){
int x;
cin >> n >> m;
for(int i = 1; i <= m; i++){
int a,b; cin >> a >> b;
g[a][b] = g[b][a] = 1;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(g[i][j]) cout << i << "------>" << j << endl;
}
}
bfs(1);
cout << endl;
memset(v,0,sizeof v);
dfs(1);
return 0;
}
/*
9 8
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
*/
临接表-链表
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
int st[N];
int n, m;
// h数组存储所有节点的边链表的头节点
// e数组存储的是节点
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
idx++;
}
void dfs(int u) {
cout << u << " ";
st[u] = 1;
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(!st[j]) dfs(j);
}
}
void bfs(int u) {
queue<int> q;
q.push(u);
st[u] = 1;
cout << u << ' ';
while(!q.empty()){
int t = q.front();
q.pop();
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if(!st[j]){
cout << j << " ";
st[j] = 1;
q.push(j);
}
}
}
}
int main() {
memset(h, -1, sizeof h);
// 链式前向星
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c; cin >> a >> b;
add(a, b);
add(b, a);
}
for (int i = 1; i <= n; i++) { // 枚举每一个顶点
cout << i << "的所有边有这些："; // 枚举当前顶点的所有边
for (int j = h[i]; j != -1; j = ne[j]) {
cout << e[j] << " ";
}
cout << endl;
}
dfs(1);
cout << endl;
memset(st, 0, sizeof st);
bfs(1);
return 0;
}
/*
一个示例图： 无向图
9 8
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
*/
