poj1154 【DFS】
2024-10-18 22:48:47
LETTERS
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 8976 | Accepted: 4017 |
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.
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.
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
思路:
基础dfs,
实现代码:
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<list>
using namespace std;
#define ll long long
const int Mod = 1e9+;
const int inf = 1e9;
const int Max = 1e5+;
vector<int>vt[Max];
int dx[] = {-, , , };
int dy[] = { , , -, };
//void exgcd(ll a,ll b,ll& d,ll& x,ll& y){if(!b){d=a;x=1;y=0;}else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}}
//ll inv(ll a,ll n){ll d, x, y;exgcd(a,n,d,x,y);return (x+n)%n;} ��Ԫ
//int gcd(int a,int b) { return (b>0)?gcd(b,a%b):a; } ��С��Լ
//int lcm(int a, int b) { return a*b/gcd(a, b); } ������
int ans = ,n,m,vis[];
char mp[][]; void dfs(int x,int y,int cnt){
for(int i=;i<;i++){
int nx = dx[i] + x;
int ny = dy[i] + y;
if(nx>=&&nx<n&&ny>=&&ny<m&&vis[mp[nx][ny]-'A']==){
vis[mp[nx][ny]-'A'] = ;
ans = max(ans,cnt+);
dfs(nx,ny,cnt+);
vis[mp[nx][ny]-'A'] = ;
}
}
} int main()
{
cin>>n>>m;
memset(vis,,sizeof(vis));
for(int i=;i<n;i++){
for(int j=;j<m;j++){
cin>>mp[i][j];
}
}
vis[mp[][]-'A'] = ;
dfs(,,);
cout<<ans<<endl;
}
最新文章
- A List of Social Tagging Datasets Made Available for Research
- Java-在线聊天系统-线程
- [Mac]Mac中显示资源库文件夹
- muParser公式库使用简介( 转)
- RMAN备份与恢复实例
- 记录使用Hibernate查询bean中字段和数据库列类型不匹配问题
- VS2012 黑色护眼主题
- .vimrc快捷键设置
- Android线程之异步消息处理机制(二)——Message、Handler、MessageQueue和Looper
- Android 从ImageView中获取Bitmap对象方法
- 对Jpa中Entity关系映射中mappedBy的理解
- 对于新版本的webstorm对vue的支持
- [No000017F]如何监控注册表的修改
- OSError: Could not find library geos_c or load any of its variants [&#39;libgeos_c.so.1&#39;, &#39;libgeos_c.so
- asp.net url址址中中文汉字参数传递乱码解决方法
- ubunttu-sh: 1: pause: not found
- 2017年12月16日 ASP.NET基本用法
- uoj#276. 【清华集训2016】汽水(分数规划+点分治)
- Courses on Turbulence
- 97-2016年11月1日AUDUSD在公布利率后反手做单感悟(2016.11.2)
热门文章
- Apache cxf暴露接口以及客户端调用之WebService初步理解
- LiveCharts文档-1前言
- EZ 2018 06 10 NOIP2018 模拟赛(十八)
- [Oracle][Standby][PDB]在PDB中修改参数,设置范围为 SPFILE,报 ORA-65099错误
- for循环两个略骚的写法
- Flask_admin 笔记六 modelView的内置方法
- 20min 快速着手Markdown
- centos7.4下Jira6环境部署及破解操作记录(完整版)
- nginx的web缓存服务环境部署记录
- cometd简单用例