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 and only line of the output should contain the maximal number of position in the board the figure can visit.
一个单人游戏是在一个R行C列的矩形的棋盘上进行的。棋盘上的每一个位置写着大写字母（A-Z）。在游戏开始前，棋盘左上角（第一行，第一列）有一个数字。在每一次操作中，玩家可以移动这个数字到其相邻位置之一（上、下、左、右）。唯一的限制是不能访问同一个字母标记的位置两次。这个游戏的目标是尽可能多的移动。要求编写一个程序，计算一次游戏中可以访问的棋盘中的最大位置数。
输入：输入的第一行包含两个整数r和c，用一个空格间隔，1< = R，C<＝20（这里不知道为什么原文是S，但是应该是C，就改了，下句中的C同是）。下面的R行包含C个字符。每行代表棋盘中的一行。
输出：输出只包含一行，一次游戏中可以访问的棋盘中的最大位置数。
思路简析：
和迷宫的原理一样（搜索题真的突破了一个迷宫就差不多都会做了），应当用深搜看最多能搜到多少个方块，标记的时候是标记该字母 是否 访问过（这里就必须开标记数组了，不能更改地图，要遍历地图再标记，很麻烦），数组的下标可以用字母的ASCII码来表示（其实把它当下标的话，数据类型会强制转换，不必特意处理）代码奉上：
#include<cstdio> #include<algorithm> using namespace std; int r,c,sum=1,ans=1,xx[4]={1,-1,0,0},yy[4]={0,0,1,-1}; char map[25][25]; bool mark[100];//标记，大写字母的ASCII码是从65到90，定100差不多，但是不要定成26了 bool check(int x,int y)//这里想着反正判断那里还要写这个函数，于是就把所有判断条件全放进来了，不像之前那样只判断出界 { if(x>=0&&y>=0&&x<r&&y<c&&!mark[map[x][y]]) return 1; return 0; } void dfs(int x,int y) { for(int i=0;i<4;i++) if(check(x+xx[i],y+yy[i])) { mark[map[x+xx[i]][y+yy[i]]]=1; //标记并且可以到达的位置数量+1 sum++; dfs(x+xx[i],y+yy[i]); ans=max(ans,sum); //每次算出来可以到达的位置数量取大 sum--; //回溯一步 mark[map[x+xx[i]][y+yy[i]]]=0; } } int main() { scanf("%d%d",&r,&c); for(int i=0;i<r;i++) scanf("%s",map[i]); mark[map[0][0]]=1; dfs(0,0); printf("%d",ans); }补充一点题外话：说出来你们可能不信，真的做这道题做了好久都编译错误，真的无语。查了半天不知道我的y1数组不知怎么惹到OpenJudge了，把数组名改成yy就过了/无奈/
