字母游戏(搜索)

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

时间限制: 10 Sec  内存限制: 64 MB
提交: 28  解决: 17
[提交] [状态] [讨论版] [命题人:外部导入]

题目描述

一种单人玩的游戏,规则为:
在一个R行C列的方格上,每个方格中有一个A~Z的字母。游戏从左上角(第一行,第一列)位置开始,一步一步地向相邻(上、下、左、右)方格移动。唯一的限制是路径上的方格中的字母,每种字母只能出现1次。
游戏的目标是走尽可能长的路径。请你写程序算出指定棋盘上,可能走的最长步数。

 

输入

第1行两个整数R和C(1≤R,C≤20);
后面R行每行有C个字母,每行表示棋盘上的一行状态。

 

输出

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

 

样例输入

5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

样例输出

10
思路:爆搜即可。
#include<bits/stdc++.h>
#include<map>
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;
}

 

上一篇:980. Unique Paths III


下一篇:POJ2728——最优比例生成树