Title: "[[Train-2]]"
Contest: lanqiao
tags:
- Contest
theme: 暴力
Create Time: 2024-04-03
status: DONE
Author:
- AllenYGY
- DFS
created: 2024-04-03T15:12
updated: 2024-04-08T23:34
ans; //答案,常常用全局变量表示
void dfs(层数,其他参数){
if (到达目的地、或者出局){ //到达最底层,或者满足条件退出
更新答案ans; //答案一般用全局变量表示,ans是最优解
return; //递归返回,即返回到上一层
}
(剪枝) //在进一步DFS之前剪枝
for (用i遍历下一层所有可能的情况) //对每一个情况继续DFS
if (used[i] == 0) { //如果状态i没有处理过,就可以进入下一层dfs
used[i] = 1; //标记状态i为已经使用,在后续dfs时不能再使用
dfs(层数+1,其他参数); //下一层,即搜小规模后继续dfs
used[i] = 0; //恢复状态i,回溯时,不影响上一层对这个状态的使用
}
return; //返回到上一层
}
#include<bits/stdc++.h>
using namespace std;x
int n;
int vis[10]; // 访问标记
int a[10]; //需要做全排列的数组
int b[10]; //当前DFS得到的全排列
void dfs(int step) {
if (step == n+1) { //已经对n个数做了全排列,输出全排列
for (int i=1; i<=n; i++)
printf("%5d",b[i]);
printf("\n");
return; //结束,不再继续DFS
}
for (int i = 1; i <= n; i++) { //遍历每个a[i],放进全排列中
if (vis[i] == 0) { // 数字a[i]不在前面得到的排列中
b[step] = a[i]; // 把a[i]放进排列
vis[i] = 1; // 保存现场:a[i]不能在后面继续用
dfs(step+1); // 继续把后面的数放进排列
vis[i] = 0; // 恢复现场:a[i]重新可以使用
}
}
return;
}
int main() {
cin >> n;
for (int i=1; i<=n; i++) a[i]=i; //赋值得到n个数
dfs(1); //对a[1]~a[n]做全排列
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //四个方向
char g[100][100];
int n = 30, m = 60;
int dfs(int x, int y){ //当前位于坐标[x,y]
if (g[x][y] == '0') return 0;
g[x][y] = '0'; //把这个点从1改为0,后面不再搜它
int ans = 1; //统计这个连通块的大小
for (int i = 0; i < 4; i++ ) { //遍历它的4个邻接
int nx = x + dx[i], ny = y + dy[i]; //一个邻居的坐标
if (nx<0 || ny<0 || nx>=n || ny>=m) continue; //这个邻居是否在边界内
ans += dfs(nx, ny);
}
return ans;
}
int main(){
for (int i = 0; i < n; i++ ) cin >> g[i];
int ans = 0;
for (int i = 0; i < n; i++ )
for (int j = 0; j < m; j++ )
if (g[i][j] == '1')
ans = max(ans, dfs(i, j));
cout << ans;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char mp[N][N]; //地图
int vis[N][N]={0}; //标记是否搜过
int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; //四个方向
int flag; //用于标记这个岛中是否被完全淹没
void dfs(int x, int y){
vis[x][y] = 1; //标记这个'#'被搜过。注意为什么放在这里
if( mp[x][y+1]=='#' && mp[x][y-1]=='#' &&
mp[x+1][y]=='#' && mp[x-1][y]=='#' )
flag = 1; //上下左右都是陆地,这是一个高地,不会淹没
for(int i = 0; i < 4; i++){ //继续DFS周围的陆地
int nx = x + d[i][0], ny = y + d[i][1];
if(vis[nx][ny]==0 && mp[nx][ny]=='#') //注意为什么要判断vis[][]
dfs(nx,ny); //继续DFS未搜过的陆地,目的是标记它们
}
}
int main(){
int n; cin >> n;
for (int i = 0; i < n; i++) cin >> mp[i];
int ans = 0 ;
for(int i = 0; i < n; i++) //DFS所有像素点
for(int j = 0; j < n; j++)
if(mp[i][j]=='#' && vis[i][j]==0){
flag = 0; //假设这个岛被淹
dfs(i,j); //找这个岛中有没有高地,如果有,置flag=1
if(flag == 0) ans++; //这个岛确实被淹了,统计被淹没岛的数量
}
cout<<ans<<endl;
return 0;
}