问题名称:更多的字母
问题描述:给出一个R*S的大写字母矩阵,一开始的位置为左上角,你可以向上下左右四个方向移动,并且不能移向曾经出现过的字母。问最多可以经过几个字母,并按字典序输出(单次的一条路线不能重复出现相同的字母。)根据给出的部分函数,写出程序中的主函数。
输入描述:第一行为两个整数,为矩阵的长和宽,即几行几列,第二行开始为矩阵的组成。
输出描述:两行,第一行表示最多经过的字母数,第二行表示按字典序输出经过的字母。
样例输入:
3 6
HFDFFB
AJHGDH
DGAGEH
样例输出:
6
A D F G H J
*/
#include
using namespace std;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
bool vis[30] = {0},A[30];
char map[30][30];
int r,s,sum,cnt;
void dfs(int x,int y){
if(cnt>sum) sum=cnt;
vis[map[x][y]-'A']=1;A[map[x][y]-'A']=1;
for(int i=0;i<4;i++){
int x1=x+dir[i][0];
int y1=y+dir[i][1];
if(x1>=1&&x1<=r&&y1>=1&&y1<=s&&!vis[map[x1][y1]-'A']){
cnt++;
A[map[x1][y1]-'A']=1;
dfs(x1,y1);
vis[map[x1][y1]-'A']=0;
cnt--;
}
}
}
int main()
{
//补全主函数!
return 0;
}
#include<iostream>
using namespace std;
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
bool vis[30] = { 0 }, A[30];
char map[30][30];
int r, s, sum, cnt;
void dfs(int x, int y) {
if (cnt > sum) sum = cnt;
vis[map[x][y] - 'A'] = 1; A[map[x][y] - 'A'] = 1;
for (int i = 0; i < 4; i++) {
int x1 = x + dir[i][0];
int y1 = y + dir[i][1];
if (x1 >= 1 && x1 <= r && y1 >= 1 && y1 <= s && !vis[map[x1][y1] - 'A']) {
cnt++;
vis[map[x1][y1] - 'A'] = 1;
dfs(x1, y1);
vis[map[x1][y1] - 'A'] = 0;
cnt--;
}
}
}
int main()
{
cin >> r >> s;
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= s; j++) {
cin >> map[i][j];
}
}
dfs(1,1);
cout << sum << endl;
for (int i = 0; i < 30; i++) {
if (A[i] == 1) cout << char('A' + i) << " ";
}
return 0;
}