当前位置:首页 > 搜索 > 正文
NOI2.5-156LETTERS
249+

题目大意:现有一个大写字母矩阵,从左上角出发,可以往上下左右四个方向走,但走过的字母不能再走,最长走多远?

题目描述

A single-player game is played on a rectangular board divided in R rows and C columns. There is a single uppercase letter (A-Z) written in every position in the board.
Before the begging of the game there is a figure in the upper-left corner of the board (first row, first column). In every move, a player can move the figure to the one of the adjacent positions (up, down,left or right). Only constraint is that a figure cannot visit a position marked with the same letter twice.
The goal of the game is to play as many moves as possible.
Write a program that will calculate the maximal number of positions in the board the figure can visit in a single game.

输入

The first line of the input contains two integers R and C, separated by a single blank character, 1 <= R, S <= 20.
The following R lines contain S characters each. Each line represents one row in the board.

输出

The first and only line of the output should contain the maximal number of position in the board the figure can visit.

样例输入

3 6
HFDFFB
AJHGDH
DGAGEH

样例输出

6

解题思路

典型的搜索回溯,从起点开始走,往4个方向试探,如果能走(是字母,且字母没走过),就走下去,长度+1,如果不能走,就退回来,不走那一步,标记该字母没访问过,再尝试另外几个方向。

赋初值:外面一圈是空字符,不能走即u[0]=1;左上角算第一步,故一开始c=ans=1。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,,,,,

NOI2.5-156LETTERS:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter