字母游戏（搜索）-白红宇

字母游戏（搜索）

阅读量：6407 次

发布时间：2019-06-23

本文共 1067 字，大约阅读时间需要 3 分钟。

问题 S: 【搜索】字母游戏

时间限制: 10 Sec 内存限制: 64 MB

提交: 28 解决: 17

[] [] [] [命题人:外部导入]

题目描述

一种单人玩的游戏，规则为：

在一个R行C列的方格上，每个方格中有一个A～Z的字母。游戏从左上角（第一行，第一列）位置开始，一步一步地向相邻（上、下、左、右）方格移动。唯一的限制是路径上的方格中的字母，每种字母只能出现1次。

游戏的目标是走尽可能长的路径。请你写程序算出指定棋盘上，可能走的最长步数。

输入

第1行两个整数R和C(1≤R，C≤20)；

后面R行每行有C个字母，每行表示棋盘上的一行状态。

输出

有且只有一行，你计算出的最长步数。

样例输入

复制样例数据

5 5IEFCJFHFKCFFALFHFGCFHMCHH

样例输出

10 思路：爆搜即可。

#include
     
      #include
      using namespace std;char str[30][30];int ans, d[4][2] = { {
   1,0},{-1,0},{
   0,1},{
   0,-1} },n,m;int vis[30];void dfs(int x,int y,int cur) {    if (cur > ans)ans = cur;    for (int i = 0; i < 4; i++) {        int cx = x + d[i][0], cy = y + d[i][1];        if (cx > n || cy > m || cx < 1 || cy < 1 || vis[str[cx][cy] - 'A'] == 1)continue;        vis[str[cx][cy] - 'A'] = 1;        dfs(cx, cy, cur + 1);        vis[str[cx][cy] - 'A'] = 0;    }    return;}int main() {    cin >> n >> m;    for (int i = 1; i <= n; i++)scanf("%s",str[i] + 1);    vis[str[1][1] - 'A'] = 1;    dfs(1, 1, 1);    cout << ans << endl;}

转载于:https://www.cnblogs.com/czy-power/p/10358675.html

你可能感兴趣的文章