@[xiangzhenze611](/user/1005749) [P1219](https://www.luogu.com.cn/problem/P1219)
by DFs_YYDS @ 2024-04-20 19:23:42
@[xiangzhenze611](/user/1005749) [BFS](https://www.luogu.com.cn/problem/B3625)
by DFs_YYDS @ 2024-04-20 19:24:52
@[DFs_YYDS](/user/1119406) thx
by xiangzhenze611 @ 2024-04-20 19:25:17
@[xiangzhenze611](/user/1005749)
上代码！
BFS迷宫最短路↓
```cpp
#include <bits/stdc++.h>
using namespace std;
struct node{
int x, y;
};
char a[51][51];
bool vis[51][51];
int cnt[51][51];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int n, m;
bool check(int x, int y){
if (x < 1 || x > n || y < 1 || y > n || a[x][y] == '0' || vis[x][y] == 1)
return false;
else
return true;
}
int main(){
int sx, sy, ex, ey, minn = 1e9;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
cin >> sx >> sy >> ex >> ey;
queue<node> q;
q.push({sx, sy});
while (!q.empty()){
node t = q.front();
q.pop();
if (vis[t.x][t.y] == 1)
continue;
vis[t.x][t.y] = 1;
if (t.x == ex && t.y == ey)
minn = min(minn, cnt[t.x][t.y]);
for (int i = 0; i < 4; i++){
int tx = t.x + dx[i];
int ty = t.y + dy[i];
if (check(tx, ty)){
q.push({tx, ty});
cnt[tx][ty] = cnt[t.x][t.y] + 1;
}
}
}
if (minn == 1e9)
cout << -1;
else
cout << minn;
return 0;
}
```
图上广搜↓
```
#include <bits/stdc++.h>
using namespace std;
bool g[101][101], vis[101];
int main(){
int n;
cin >> n;
for (int i = 1; i <= n; i++){
int u1, u2;
cin >> u1 >> u2;
g[u1][u2] = 1;
g[u2][u1] = u1;
}
queue<int> q;
q.push(1);
while (!q.empty()){
int t = q.front();
q.pop();
if (vis[t])
continue;
vis[t] = true;
cout << t;
for (int i = 1; i <= 100; i++)
if (g[t][i])
q.push(i);
}
return 0;
}
```
DFS联通块↓
```cpp
#include <bits/stdc++.h>
using namespace std;
char a[101][101];
bool vis[101][101];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int n, m, cnt = 0;
void dfs(int x, int y){
if (x < 1 || x > n || y < 1 || y > m || a[x][y] == '.' || vis[x][y] == 1)
return ;
vis[x][y] = 1;
for (int i = 0; i < 4; i++)
dfs(x + dx[i], y + dy[i]);
}
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (vis[i][j] == 0 && a[i][j] == 'W'){
dfs(i, j);
cnt++;
}
cout << cnt;
return 0;
}
```
DFS图搜↓
```cpp
#include <bits/stdc++.h>
using namespace std;
bool g[101][101], vis[101];
void dfs(int n){
if (vis[n])
return ;
cout << n << " ";
vis[n] = true;
for (int i = 1; i <= 101; i++)
if (g[n][i])
dfs(i);
}
int main(){
int n;
cin >> n;
for (int i = 1; i <= n; i++){
int u1, u2;
cin >> u1 >> u2;
g[u1][u2] = 1;
g[u2][u1] = u1;
}
dfs(1);
return 0;
}
```
DFS排列组合↓
```cpp
#include <bits/stdc++.h>
using namespace std;
int a[1001], n;
bool vis[1001];
void dfs(int p){
if (p > n){
for (int i = 1; i <= n; i++)
if (vis[i])
cout << a[i] << " ";
cout << endl;
return ;
}
for (int i = 1; i >= 0; i--){
vis[p] = i;
dfs(p + 1);
}
return ;
}
int main(){
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
dfs(1);
return 0;
}
```
互关吗？
by xpg007 @ 2024-04-20 20:55:00
@[xpg007](/user/1024680) 我是要题目，不是要代码
by xiangzhenze611 @ 2024-04-20 20:56:21
@[xiangzhenze611](/user/1005749)
emmm............
by xpg007 @ 2024-04-20 21:02:08
@[xiangzhenze611](/user/1005749)
[全在这里](https://www.luogu.com.cn/problem/list?tag=4,126,127,128,129,131,135,134,133,132,136,137,396&page=1)
by xpg007 @ 2024-04-20 21:02:56