记录51
#include<bits/stdc++.h> using namespace std; char mp[1010][1010]={}; int vis[1010][1010]={}; int dx[5]={0,1,0,-1}; int dy[5]={1,0,-1,0}; int main(){ int T,n,m,k,x,y,d; cin>>T; while(T--){ cin>>n>>m>>k; cin>>x>>y>>d; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) cin>>mp[i][j]; } int ans=1; vis[x][y]=1; //int cnt=1; while(k--){ //printf("第%d次操作:",cnt); int xn=x+dx[d]; int yn=y+dy[d]; if(xn>=1&&xn<=n&&yn>=1&yn<=m&&mp[xn][yn]=='.'){ if(vis[xn][yn]==0){ ans++; vis[xn][yn]=1; } x=xn; y=yn; //printf("走到(%d,%d) 第%d个位置\n",xn,yn,ans); } else{ d=++d%4; //printf("向%d方向转向\n",d); } //cnt++; } cout<<ans<<endl; memset(vis,0,sizeof(vis)); } return 0; }题目传送门https://www.luogu.com.cn/problem/P11228
突破口
初始时，机器人的位置为 (x0,y0)，朝向为 d0。保证初始时机器人所在的位置为空地。接下来机器人将要进行 k 次操作。每一步，机器人将按照如下的模式操作
👉转向也算一次操作
保证字符串中只包含 x 和 . 两个字符。其中，第 x 行的字符串的第 y 个字符代表的位置为 (x,y)。这个位置是 x 即代表它是障碍，否则代表它是空地。数据保证机器人初始时所在的位置为空地。
👉有障碍物
地图上所有被机器人经过的位置（包括起始位置）有几个。
👉计算走的格子数，不重复计数
思路
并不是bfs跟dfs的题目，但是如果会搜索就很轻松做本题，这题纯模拟
- 构建地图
- 寻找可行路径
- 计数走过的格子
代码简析
#include<bits/stdc++.h> using namespace std; char mp[1010][1010]={}; int vis[1010][1010]={}; int dx[5]={0,1,0,-1}; int dy[5]={1,0,-1,0}; int main(){ int T,n,m,k,x,y,d; cin>>T; while(T--){ cin>>n>>m>>k; cin>>x>>y>>d; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) cin>>mp[i][j]; } } ... return 0; }char mp[1010][1010]={};👉地图空间
int vis[1010][1010]={};👉判断地图上的点是否访问过，防止重复计数
int dx[5]={0,1,0,-1};👉x方向移动，上(减)下(加)移动
int dy[5]={1,0,-1,0};👉y方向移动，左(减)右(加)移动
注意：二者结合起来看，就是右下左上的逆时针转动
int T（几组数据）,n（行数）,m（列数）,k（次数）,x（停留的点）,y（停留的点）,d（转动方向）;
#include<bits/stdc++.h> using namespace std; char mp[1010][1010]={}; int vis[1010][1010]={}; int dx[5]={0,1,0,-1}; int dy[5]={1,0,-1,0}; int main(){ int T,n,m,k,x,y,d; cin>>T; while(T--){ cin>>n>>m>>k; cin>>x>>y>>d; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) cin>>mp[i][j]; } int ans=1; vis[x][y]=1; //int cnt=1; while(k--){ //printf("第%d次操作:",cnt); int xn=x+dx[d]; int yn=y+dy[d]; if(xn>=1&&xn<=n&&yn>=1&yn<=m&&mp[xn][yn]=='.'){ if(vis[xn][yn]==0){ ans++; vis[xn][yn]=1; } x=xn; y=yn; //printf("走到(%d,%d) 第%d个位置\n",xn,yn,ans); } else{ d=++d%4; //printf("向%d方向转向\n",d); } //cnt++; } cout<<ans<<endl; memset(vis,0,sizeof(vis)); } return 0; }int ans=1;👉起点是经过的第一个格子
vis[x][y]=1;👉地图上记录起点访问过
while(k--){}👉只执行k次操作
int xn=x+dx[d]; int yn=y+dy[d];👉记录接下来移动后的位置
if(xn>=1&&xn<=n&&yn>=1&yn<=m&&mp[xn][yn]=='.'){}👉判断路径是否可行
ans++; vis[xn][yn]=1;👉格子数加1，同时记录这个点经过了
x=xn; y=yn;👉更新停留的点
else{d=++d%4;}👉路径不可行的时候进行转向
cout<<ans<<endl;👉输出经过的点
memset(vis,0,sizeof(vis));👉访问数组重置，防止下一组数据被污染
补充
CSP-J DFS/BFS 技巧完全汇总
一、搜索题识别特征（先判断用哪个）
特征 DFS（深度优先） BFS（广度优先） 目标 找路径、方案数、连通块 找最短路径/步数、最小操作 数据结构 图、树、网格 图、网格 关键词 "有多少种方案"、"路径"、"连通" "最少步数"、"最短"、"最快" 典型题 迷宫路径数、连通块、选物品 迷宫最短路径、倒水问题、编辑距离 CSP-J频率 ★★★★★ ★★★★★ 二、DFS核心技巧（CSP-J必背）
技巧1：记忆化搜索（DP化）
场景：重复子问题，如迷宫路径数
int dfs(int x, int y) { if (x == n && y == m) return 1; if (vis[x][y]) return dp[x][y]; // 记忆化 vis[x][y] = true; int ans = 0; for (int dir = 0; dir < 4; dir++) { int nx = x + dx[dir], ny = y + dy[dir]; if (valid(nx, ny)) { ans += dfs(nx, ny); } } return dp[x][y] = ans; // 保存结果 }作用：将O(4ⁿ)降到O(n²)
技巧2：连通块标记（最常用）
场景：统计岛屿数量、洪水填充
void dfs(int x, int y) { if (x<1 || x>n || y<1 || y>m || a[x][y]!=1) return; // 边界 a[x][y] = 2; // 标记为已访问 for (int dir=0; dir<4; dir++) { dfs(x+dx[dir], y+dy[dir]); } } // 统计连通块 int cnt = 0; for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) if (a[i][j] == 1) { dfs(i, j); cnt++; }技巧3：选物品/组合（回溯+剪枝）
场景：从n个物品选k个，和为目标值
bool dfs(int idx, int sum, int chosen) { if (chosen == k && sum == target) return true; if (idx > n || chosen > k || sum > target) return false; // 剪枝 // 选当前 if (dfs(idx+1, sum+a[idx], chosen+1)) return true; // 不选当前 if (dfs(idx+1, sum, chosen)) return true; return false; }技巧4：树形DFS（树遍历）
场景：树的深度、子树大小、路径和
int depth[N]; void dfs(int u, int parent) { for (int v : g[u]) { if (v == parent) continue; // 避免回父节点 depth[v] = depth[u] + 1; dfs(v, u); } }三、BFS核心技巧（CSP-J必背）
技巧1：最短路径（最核心）
场景：迷宫最短步数、最少操作
int bfs(int sx, int sy) { queue<pair<int, int>> q; q.push({sx, sy}); vis[sx][sy] = 0; // 距离数组 while (!q.empty()) { auto [x, y] = q.front(); q.pop(); if (x == tx && y == ty) return vis[x][y]; for (int dir=0; dir<4; dir++) { int nx = x + dx[dir], ny = y + dy[dir]; if (valid(nx, ny) && !vis[nx][ny]) { vis[nx][ny] = vis[x][y] + 1; q.push({nx, ny}); } } } return -1; // 无法到达 }记忆：BFS第一次到达终点时，步数一定是最短的
技巧2：多源BFS（洪水填充优化）
场景：多个起点同时扩展
// 将所有起点同时入队 queue<pair<int, int>> q; for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) if (a[i][j] == 起点) { q.push({i, j}); vis[i][j] = 0; } // BFS扩展，谁先到终点谁最短 while (!q.empty()) { ... }技巧3：0-1 BFS（边权为0或1）
场景：某些方向代价为0，某些为1（如转向代价）
deque<pair<int, int>> q; // 用双端队列 vis[sx][sy] = 0; q.push_front({sx, sy}); // 起点从队首入 while (!q.empty()) { auto [x, y] = q.front(); q.pop_front(); for (int dir=0; dir<4; dir++) { int nx = x + dx[dir], ny = y + dy[dir]; int w = (dir == 方向) ? 0 : 1; // 代价 if (valid(nx, ny) && vis[x][y] + w < vis[nx][ny]) { vis[nx][ny] = vis[x][y] + w; if (w == 0) q.push_front({nx, ny}); else q.push_back({nx, ny}); } } }四、DFS vs BFS 选择决策树
是否需要求最短/最少？ ├── 是 → BFS（第一次到终点即最短） │ └── 边权为0/1 → 0-1 BFS/双端队列 │ └── 否 → DFS（找路径、方案数、连通块） ├── 有重复子问题 → 记忆化搜索 ├── 找所有方案 → 回溯+剪枝 └── 只需遍历 → 普通DFS五、CSP-J搜索题通用模板
DFS模板（连通块）
const int N = 1010; int n, m, a[N][N]; bool vis[N][N]; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; void dfs(int x, int y) { if (x<1 || x>n || y<1 || y>m || a[x][y]==0 || vis[x][y]) return; vis[x][y] = true; for (int dir=0; dir<4; dir++) { dfs(x+dx[dir], y+dy[dir]); } }BFS模板（最短路径）
int bfs(int sx, int sy, int tx, int ty) { memset(vis, -1, sizeof(vis)); queue<pair<int, int>> q; q.push({sx, sy}); vis[sx][sy] = 0; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); if (x == tx && y == ty) return vis[x][y]; for (int dir=0; dir<4; dir++) { int nx = x + dx[dir], ny = y + dy[dir]; if (nx>=1 && nx<=n && ny>=1 && ny<=m && a[nx][ny]==1 && vis[nx][ny]==-1) { vis[nx][ny] = vis[x][y] + 1; q.push({nx, ny}); } } } return -1; // 无法到达 }六、性能优化技巧
1. 剪枝（Pruning）
if (当前步数 >= 最优解) return; // 步数剪枝 if (当前和 > 目标值) return; // 和剪枝 if (不可能到达) return; // 可行性剪枝2. 迭代加深（DFS深度限制）
for (int depth = 1; depth <= MAX_DEPTH; depth++) { if (dfs(起点, depth)) { // 限制深度搜索 cout << depth; // 找到最优解 break; } }3. 双向BFS
// 从起点和终点同时开始BFS，在中间相遇 queue<pair<int, int>> q1, q2; // 交替扩展，直到相遇七、调试与容错技巧
1. 访问越界检查
#define valid(x, y) (x>=1 && x<=n && y>=1 && y<=m && !vis[x][y]) // 或函数形式 inline bool check(int x, int y) { return x>=1 && x<=n && y>=1 && y<=m && a[x][y]==1; }2. 递归深度限制
// DFS递归深度超过10^5会栈溢出，改用栈模拟迭代 if (depth > 100000) return false; // 提前退出3. BFS队列大小
// 最坏情况队列大小 = n×m，开数组要开够 queue<pair<int, int>> q; // 或用数组模拟队列八、CSP-J高频搜索题清单
年份 题目 搜索类型 难度 2023 T1 小苹果 流程模拟（类BFS） ★☆☆☆☆ 2022 T1 乘方 DFS（递归） ★☆☆☆☆ 2021 迷宫 BFS最短路径 ★★☆☆☆ 2020 连通块 DFS染色 ★★☆☆☆ 2019 选物品 DFS回溯 ★★☆☆☆ 九、一句话总结
CSP-J搜索题 = 先判BFS/DFS → 写模板 → 加剪枝 → 防越界 → 调试输出，BFS找最短，DFS找路径，记忆化防超时，全局开大数组。
