哈尔滨营销网站建设公司,网站开发维护干嘛,响应式网页设计图片,深圳定制网站建设【题目来源】https://www.acwing.com/problem/content/1113/【题目描述】 给定一个 RS 的大写字母矩阵#xff0c;你的起始位置位于左上角#xff0c;你可以向上下左右四个方向进行移动#xff0c;但是不能移出边界#xff0c;或者移动到曾经经过的字母#xff08;左上角字…【题目来源】https://www.acwing.com/problem/content/1113/【题目描述】 给定一个 R×S 的大写字母矩阵你的起始位置位于左上角你可以向上下左右四个方向进行移动但是不能移出边界或者移动到曾经经过的字母左上角字母看作第一个经过的字母。 请问你最多可以经过几个字母。【输入格式】 第一行包含两个整数 R 和 S表示字母矩阵的行和列。 接下来 R 行每行包含一个长度为 S 的大写字母构成的字符串共同构成字母矩阵。【输出格式】 输出一个整数表示最多能够经过的字母个数。【数据范围】 1≤R,S≤20【输入样例】 3 6 HFDFFB AJHGDH DGAGEH【输出样例】 6【算法分析】 要注意的是这里的 st 数组不是标记走过的格子而是标记字母是否被访问过。 【算法代码dfs】
#include bits/stdc.h
using namespace std;int n,m;
int st[26];
int ans-0x3f3f3f3f;
int dx[]{-1,0,1,0};
int dy[]{0,1,0,-1};
vectorstring v;void dfs(int x,int y,int step){int idxv[0][0]-A;st[idx]1;for(int i0;i4;i){int nxxdx[i];int nyydy[i];if(nx0 nxn ny0 nym){int idxv[nx][ny]-A;if(st[idx]1) continue;st[idx]1;dfs(nx,ny,step1);st[idx]0;}}ansmax(ans,step);return;
}int main(){cinnm;for(int i0;in;i){string s;cins;v.push_back(s);}dfs(0,0,1);coutansendl;return 0;
}/*
in
3 6
HFDFFB
AJHGDH
DGAGEHout:
6
*/
【算法代码bfs】
#include bits/stdc.h
using namespace std;int n,m;
int ans-0x3f3f3f3f;
int dx[]{-1,0,1,0};
int dy[]{0,1,0,-1};
vectorstring v;struct MAP{int x;int y;int st[26];int step;
};void bfs() {queueMAP Q;MAP s;memset(s.st,0,sizeof(s.st));s.st[v[0][0]-A]1;s.step1;s.x0;s.y0;Q.push(s);while(Q.size()){MAP tQ.front();Q.pop();ansmax(ans,t.step);for(int i0;i4;i){int nxt.xdx[i];int nyt.ydy[i];if(nx0 nxn ny0 nym){int idxv[nx][ny]-A;if(t.st[idx]1) continue;MAP next;next.xnx;next.yny;next.stept.step1;memcpy(next.st, t.st, sizeof(t.st));next.st[idx]1;Q.push(next);}}}
}int main() {cinnm;for(int i0;in;i){string s;cins;v.push_back(s);}bfs();coutansendl;return 0;
}/*
in
3 6
HFDFFB
AJHGDH
DGAGEH out:
6
*/
【参考文献】https://www.acwing.com/solution/content/15385/
