洛谷-算法1-7-搜索4

P1596 [USACO10OCT] Lake Counting S题目描述由于最近的降雨水在农夫约翰的田地里积聚了。田地可以表示为一个 N×M 的矩形1≤N≤1001≤M≤100。每个方格中要么是水W要么是干地.。农夫约翰想要弄清楚他的田地里形成了多少个水塘。一个水塘是由连通的水方格组成的其中一个方格被认为与它的八个邻居相邻。给定农夫约翰田地的示意图确定他有多少个水塘。输入格式第 1 行两个用空格分隔的整数N 和 M。第 2 行到第 N1 行每行 M 个字符表示农夫约翰田地的一行。每个字符要么是W要么是.。字符之间没有空格。输出格式第 1 行农夫约翰田地中的水塘数量。显示翻译题意翻译输入输出样例输入 #1复制10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.输出 #1复制3说明/提示输出详情共有三个水塘一个在左上角一个在左下角还有一个沿着右侧。由 ChatGPT 4o 翻译实现代码#includebits/stdc.h using namespace std; int n,m,sum; char a[111][111]; int ac[111][111]; int dx[8]{0, 0, 1, 1,-1,-1,1,-1}; int dy[8]{1,-1, 1,-1, 1,-1,0, 0}; void dfs(int x,int y){ ac[x][y]1; for(int i0;i8;i){ if(a[xdx[i]][ydy[i]]Wac[xdx[i]][ydy[i]]0){ dfs(xdx[i],ydy[i]); } } } int main(){ cinnm; for(int i1;in;i){ for(int j1;jm;j){ cina[i][j]; } } for(int i1;in;i){ for(int j1;jm;j){ if(a[i][j]Wac[i][j]0){ dfs(i,j); sum; } } } coutsum; return 0; }P1162 填涂颜色题目描述由数字 0 组成的方阵中有一任意形状的由数字 1 构成的闭合圈。现要求把闭合圈内的所有空间都填写成 2。例如6×6 的方阵n6涂色前和涂色后的方阵如下如果从某个 0 出发只向上下左右 4 个方向移动且仅经过其他 0 的情况下无法到达方阵的边界就认为这个 0在闭合圈内。闭合圈不一定是环形的可以是任意形状但保证闭合圈内的 0 是连通的两两之间可以相互到达。0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 1 0 1 1 1 1 1 1 10 0 0 0 0 0 0 0 0 1 1 1 0 1 1 2 2 1 1 1 2 2 2 1 1 2 2 1 2 1 1 1 1 1 1 1输入格式每组测试数据第一行一个整数 n(1≤n≤30)。接下来 n 行由 0 和 1 组成的 n×n 的方阵。方阵内只有一个闭合圈圈内至少有一个 0。输出格式已经填好数字 2 的完整方阵。输入输出样例输入 #1复制6 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1输出 #1复制0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 2 2 1 1 1 2 2 2 1 1 2 2 2 2 1 1 1 1 1 1 1说明/提示对于 100% 的数据1≤n≤30。实现代码#includebits/stdc.h using namespace std; int n; int a[33][33]; int mark[33][33]; int dx[4]{0,0,1,-1}; int dy[4]{-1,1,0,0}; struct node{ int x,y; }; int main(){ cinn; for(int i1;in;i){ for(int j1;jn;j){ cina[i][j]; } } mark[0][0]1; queuenode q; node tp{0,0},pp; q.push(tp); while(q.size()){ node pq.front(); q.pop(); for(int i0;i4;i){ int nxp.xdx[i]; int nyp.ydy[i]; if(nx0nxn1ny0nyn1){ if(a[nx][ny]0mark[nx][ny]0){ mark[nx][ny]1; pp{nx,ny}; q.push(pp); } } } } for(int i1;in;i){ for(int j1;jn;j){ if(a[i][j]0mark[i][j]0){ cout2 ; } else couta[i][j] ; } coutendl; } return 0; }P1032 [NOIP 2002 提高组] 字串变换疑似错题题目背景本题不保证存在靠谱的多项式复杂度的做法。测试数据非常的水各种做法都可以通过不代表算法正确。因此本题题目和数据仅供参考。本题为搜索题本题不接受 hack 数据。关于此类题目的详细内容题目描述已知有两个字串 A,B 及一组字串变换的规则至多 6 个规则形如A1​→B1​。A2​→B2​。规则的含义为在 A 中的子串 A1​ 可以变换为 B1​A2​ 可以变换为 B2​⋯。例如AabcdBxyz变换规则为abc→xuud→yy→yz。则此时A 可以经过一系列的变换变为 B其变换的过程为abcd→xud→xy→xyz。共进行了 3 次变换使得 A 变换为 B。输入格式第一行有两个字符串 A,B。接下来若干行每行有两个字符串 Ai​,Bi​表示一条变换规则。输出格式若在 10 步包含 10 步以内能将 A 变换为 B则输出最少的变换步数否则输出NO ANSWER!。输入输出样例输入 #1复制abcd xyz abc xu ud y y yz输出 #1复制3说明/提示对于 100% 数据保证所有字符串长度的上限为 20。【题目来源】NOIP 2002 提高组第二题实现代码#include iostream #include string using namespace std; string a,b; string ra[7],rb[7]; struct node{ string cur; int cs; }q[2000000]; int main() { cinab; int i1; while(cinra[i]rb[i]) { i; } i-1; int head0,tail1; q[tail].cura; q[tail].cs0; while(headtail) { head; if(q[head].cs10) { coutNO ANSWER!endl; return 0; } for(int j1;ji;j) { int posq[head].cur.find(ra[j],0); while(1) { if(pos-1) { break; } else { tail; q[tail].curq[head].cur; q[tail].csq[head].cs1; q[tail].cur.replace(pos,ra[j].size(),rb[j]); if(q[tail].curb) { coutq[tail].cs; return 0; } posq[head].cur.find(ra[j],pos1); } } } } return 0; }P1825 [USACO11OPEN] Corn Maze S题目描述去年秋天农夫约翰带着奶牛们参观了一个玉米迷宫。但这不是一个普通的玉米迷宫它有几个重力驱动的传送滑梯可以让奶牛瞬间从迷宫中的一个点传送到另一个点。滑梯是双向的奶牛可以瞬间从滑梯的起点滑到终点或者从终点滑到起点。如果奶牛踩到滑梯的任一端她必须使用滑梯。传送操作不能连续使用即传送一次之后必须通过非传送方式移动至少一步才能再次进行传送。玉米迷宫的外部完全由玉米包围只有一个出口。迷宫可以用一个 N×M2≤N≤3002≤M≤300的网格表示。每个网格元素包含以下项目之一玉米玉米网格元素不可通行草地容易通过滑梯端点会将奶牛传送到另一个端点出口奶牛只能从一个空间移动到相邻的下一个空间前提是它们相邻且都不包含玉米。每个草地空间有四个潜在的邻居可以让奶牛到达。从一个草地空间移动到相邻空间需要 1 个时间单位从一个滑梯端点移动到另一个端点需要 0 个时间单位。填满玉米的空间用井号#表示。草地空间用英文句号.表示。滑梯端点对用相同的大写字母A到Z表示并且没有两个不同的滑梯端点用相同的字母表示。出口用等号表示。贝茜迷路了。她知道自己在网格中的位置并用「at」符号标记了她当前的草地空间。她需要的最短时间是多少才能移动到出口空间输入格式第一行两个用空格隔开的整数 N 和 M。第 2∼N1 行第 i1 行描述了迷宫中的第 i 行的情况共有 M 个字符每个字符之间没有空格。输出格式一个整数表示起点到出口所需的最短时间。显示翻译题意翻译输入输出样例输入 #1复制5 6 ##### #.W.## #.#### #.W## ######输出 #1复制3说明/提示例如以下矩阵N5,M6。##### #.W.## #.#### #.W## ######唯一的一个装置的结点用大写字母 W 表示。最优方案为先向右走到装置的结点花费一个单位时间再到装置的另一个结点上花费 0 个单位时间然后再向右走一个再向上走一个到达出口处总共花费了 3 个单位时间。由 ChatGPT 4o 翻译实现代码#includeiostream #includequeue using namespace std; const int N350; struct point{ int x; int y; int t; }; queuepoint que; char a[N][N]; bool vis[N][N]; int n,m; int dx[4]{1,0,-1,0}; int dy[4]{0,1,0,-1}; int sx; int sy; void goto_another(int nx,int ny,int k) { for(int i1;in;i) { for(int j1;jm;j) { if(a[i][j]a[nx][ny](i!nx||j!ny)) { nxi; nyj; return ; } } } } int main() { cinnm; string s; for(int i1;in;i) { cins; for(int j1;jm;j) { a[i][j]s[j-1]; if(a[i][j]) { sxi; syj; } } } que.push((point){sx,sy,0}); while(!que.empty()) { point fque.front(); que.pop(); if(a[f.x][f.y]) { coutf.t; return 0; } if(a[f.x][f.y]Aa[f.x][f.y]Z) { goto_another(f.x,f.y,f.t); } for(int i0;i3;i) { int nxf.xdx[i]; int nyf.ydy[i]; if(nx1nxnny1nyma[nx][ny]!#!vis[nx][ny]) { vis[nx][ny]true; que.push((point){nx,ny,f.t1}); } } } return 0; }