Description
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.
Input
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.
Output
The first and only line of the output should contain the maximal number of position in the board the figure can visit.
Sample Input
3 6
HFDFFB
AJHGDH
DGAGEH
Sample Output
6
Water DFS
LANGUEGE:C++
CODE:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 30
const int dir[8][2]={{1,0},{0,1},{-1,0},{0,-1}};
bool used[maxn];
int n,m;
char matrix[maxn][maxn],cnt,max;
void dfs(int x,int y)
{
for(int i=0;i<4;i++)
{
int x1=x+dir[i][0];
int y1=y+dir[i][1];
if(x1>0&&x1<=n&&y1>0&&y1<=m&&!used[matrix[x1][y1]])
{
used[matrix[x1][y1]]=true;
cnt++;
dfs(x1,y1);
if(cnt>max)max=cnt;
used[matrix[x1][y1]]=false;
cnt--;
}
}
}
int main()
{
char s[maxn];
while(scanf("%d%d",&n,&m)!=EOF)
{
getchar();
cnt=1,max=1;
for(int i=1;i<=n;i++)
{
gets(s);
for(int j=0;j<m;j++)
{
matrix[i][j+1]=s[j]-'A'+1;
}
}
used[matrix[1][1]]=true;
dfs(1,1);
used[matrix[1][1]]=false;
printf("%d\n",max);
}
return 0;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj分类poj分类poj分类poj分类
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告