深度优先搜索
2026-07-19 20:41:44
发布于：广东
121阅读
0回复
0点赞
文件读写
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
int a,b;
cin>>a>>b;
int ans = 0;
for(int i=1;i<=a+b;i++)ans++;
cout<<ans;
fclose(stdin);
fclose(stdout);
return 0;
}
全排类失败代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
if(n==1){
cout<<1;
}if(n==2){
cout<<1<<' '<<2<<endl<<2<<' '<<1;
}if(n==3){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int o=1;o<=n;o++){
if(i==j||j==o||i==o)continue;
cout<<i<<' '<<j<<' '<<o<<' '<<endl;
}
}
}
}if(n==4){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int o=1;o<=n;o++){
for(int k=1;k<=n;k++){
if(o==k||j==k||i==k||i==j||j==o||i==o)continue;
cout<<i<<' '<<j<<' '<<o<<' '<<k<<endl;
}
}
}
}
}if(n==5){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int o=1;o<=n;o++){
for(int k=1;k<=n;k++){
for(int q=1;q<=n;q++){
if(k==q||o==q||j==q||i==q||o==k||j==k||i==k||i==j||j==o||i==o)continue;
cout<<i<<' '<<j<<' '<<o<<' '<<k<<' '<<q<<endl;
}
}
}
}
}
}if(n==6){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int o=1;o<=n;o++){
for(int k=1;k<=n;k++){
for(int q=1;q<=n;q++){
for(int z=1;z<=n;z++){
if(q==z||k==z||o==z||j==z||i==z||k==q||o==q||j==q||i==q||o==k||j==k||i==k||i==j||j==o||i==o)continue;
cout<<i<<' '<<j<<' '<<o<<' '<<k<<' '<<q<<' '<<z<<endl;
}
}
}
}
}
}
}if(n==7){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int o=1;o<=n;o++){
for(int k=1;k<=n;k++){
for(int q=1;q<=n;q++){
for(int z=1;z<=n;z++){
for(int a=1;a<=n;a++){
if(i==a||j==a||o==a||k==a||q==a||z==a||q==z||k==z||o==z||j==z||i==z||k==q||o==q||j==q||i==q||o==k||j==k||i==k||i==j||j==o||i==o)continue;
cout<<i<<' '<<j<<' '<<o<<' '<<k<<' '<<q<<' '<<z<<' '<<a<<endl;
}
}
}
}
}
}
}
}if(n==8){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int o=1;o<=n;o++){
for(int k=1;k<=n;k++){
for(int q=1;q<=n;q++){
for(int z=1;z<=n;z++){
for(int a=1;a<=n;a++){
for(int b=1;b<=n;b++){
if(i==b||j==b||o==b||k==b||q==b||z==b||a==b||i==a||j==a||o==a||k==a||q==a||z==a||q==z||k==z||o==z||j==z||i==z||k==q||o==q||j==q||i==q||o==k||j==k||i==k||i==j||j==o||i==o)continue;
cout<<i<<' '<<j<<' '<<o<<' '<<k<<' '<<q<<' '<<z<<' '<<a<<' '<<b<<endl;
}
}
}
}
}
}
}
}
}
}
朋友圈
#include<bits/stdc++.h>
using namespace std;
vector<int> g[100010];
bool vis[100010];
int n,m;
void dfs(int u){
vis[u] = true;
for(int i=0;i<g[u].size();i++){
int ne = g[u][i];
if(!vis[ne]){
vis[ne] = true;
dfs(ne);
}
}
}
int main(){
cin>>n>>m;
while(m--){
int a,b;
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
int ans = 0;
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs(i);//把i相邻的朋友都访问
ans++;
}
}
cout<<ans;
return 0;
}
考试第5题
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
int sx, sy, tx, ty;
char a[N][N];
bool vis[N][N];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
void dfs(int x, int y) {
vis[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx<1 || nx>n || ny<1 || ny>m)continue;
if(vis[nx][ny])continue;
if(a[nx][ny] == '#')continue;
if(a[nx][ny] == '~')continue;
dfs(nx,ny);
}
}
int main() {
freopen("lulu1.in", "r", stdin);
freopen("lulu1.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
if (a[i][j] == 'S') {
sx = i;
sy = j;
}
if (a[i][j] == 'T') {
tx = i;
ty = j;
}
}
}
dfs(sx, sy);
if (vis[tx][ty]) {
cout << "Yes";
} else {
cout << "No";
}
return 0;
}
T6 笔记
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
int sx, sy, tx, ty;
int ans = 1e9;
char a[N][N];
bool vis[N][N];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
void dfs(int x, int y,int d) {
if(a[x][y] == 'T'){
ans=min(ans,d);
return;
}
vis[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx<1 || nx>n || ny<1 || ny>m)continue;
if(vis[nx][ny])continue;
if(a[nx][ny] == '#')continue;
if(a[nx][ny] == '~')continue;
dfs(nx,ny,d+1);
}
vis[x][y]=false;
}
int main() {
freopen("lulu2.in", "r", stdin);
freopen("lulu2.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
if (a[i][j] == 'S') {
sx = i;
sy = j;
}
if (a[i][j] == 'T') {
tx = i;
ty = j;
}
}
}
dfs(sx, sy, 0);
if (ans==1e9) {
cout << "-1";
} else {
cout << ans;
}
return 0;
}
水坑
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
int ans = 0;
char a[N][N];
int dx[] = {-1, 1, 0, 0,1,1,-1,-1};
int dy[] = {0, 0, -1, 1,1,-1,1,-1};
void dfs(int x, int y) {
a[x][y] = '.';
for (int i = 0; i < 8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx<1 || nx>n || ny<1 || ny>m)continue;
if(a[nx][ny] != 'W')continue;
dfs(nx,ny);
}
}
int main() {
freopen("shuikeng.in", "r", stdin);
freopen("shuikeng.out", "w", stdout);
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(a[i][j]=='W'){
dfs(i,j);
ans++;
}
}
}
cout<<ans;
fclose(stdin);
fclose(stdout);
return 0;
}
地图探险
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int T;
int n, m, k;
char a[N][N];
bool vis[N][N];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int main() {
freopen("explore.in", "r", stdin);
freopen("explore.out", "w", stdout);
cin >> T;
while (T--) {
cin >> n >> m >> k;
int x, y, d;
cin >> x >> y >> d;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> a[i][j];
vis[i][j] = false;
}
}
vis[x][y] = true;
while (k--) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == '.') {
x = nx;
y = ny;
vis[x][y] = true;
}
else {
d = (d + 1) % 4;
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (vis[i][j])
ans++;
cout << ans << '\n';
}
fclose(stdin);
fclose(stdout);
return 0;
}
考试T7
#include<bits/stdc++.h>
using namespace std;
int n,m,sum=0;
char mp[1010][1010];
bool vis[1010][1010];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
void dfs(int x,int y){
if(x==n&&y==m){
sum++;
return ;
}
vis[x][y]=1;
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m && mp[nx][ny]=='*' && vis[nx][ny]==0){
dfs(nx,ny);
}
}
vis[x][y]=0;
}
int main(){
freopen("tanxian.in","r",stdin);
freopen("tanxian.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
vis[1][1]=1;
dfs(1,1);
cout<<sum;
fclose(stdin);
fclose(stdout);
return 0;
}
有帮助，赞一个