dfs(最长路径)
2024-10-07 12:29:49
http://poj.org/problem?id=1154
LETTERS
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 9519 | Accepted: 4252 |
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
Source
题意:从左上角出发,每个字母不走两次的条件下,求走最多次数。
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdio.h>
#include <queue>
#include <stack>;
#include <map>
#include <set>
#include <string.h>
#include <vector>
#define ME(x , y) memset(x , y , sizeof(x))
#define SF(n) scanf("%d" , &n)
#define rep(i , n) for(int i = 0 ; i < n ; i ++)
#define INF 0x3f3f3f3f
#define mod 1000000007
using namespace std;
typedef long long ll ;
char a[][];
int n , m ;
int bx , by ;
int ans ;
int vis[];
int dir[][] = {{ , } , {- , } , { , } , { , -}}; void dfs(int x , int y , int cnt)
{
for(int i = ; i < ; i++)
{ int xx = x + dir[i][];
int yy = y + dir[i][];
if(vis[a[xx][yy] - 'A'] || xx <= || xx > n || yy <= || yy > m)
{
continue;
}
vis[a[xx][yy] - 'A'] = ;
dfs(xx , yy , cnt+); }
ans = max(ans , cnt);//for循环结束代表一条路径的结束。
vis[a[x][y] - 'A'] = ;//不同路径互不干扰
} int main()
{
while(~scanf("%d%d" , &n , &m))
{
for(int i = ; i <= n ; i++)
{
for(int j = ; j <= m ; j++)
{
cin >> a[i][j];
}
}
memset(vis , , sizeof(vis));
vis[a[][] - 'A'] = ;//将原地标记并加一
ans = ;
dfs( , , );
cout << ans << endl ;
} return ;
}
下面这个是参考学长的码。
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdio.h>
#include <queue>
#include <stack>;
#include <map>
#include <set>
#include <string.h>
#include <vector>
#define ME(x , y) memset(x , y , sizeof(x))
#define SF(n) scanf("%d" , &n)
#define rep(i , n) for(int i = 0 ; i < n ; i ++)
#define INF 0x3f3f3f3f
#define mod 1000000007
using namespace std;
typedef long long ll ;
char a[][];
int n , m ;
int ans ;
int vis[];
int dir[][] = {{ , } , {- , } , { , } , { , -}}; void dfs(int x , int y , int cnt)
{
if(vis[a[x][y] - 'A'] || x <= || y <= || x > n || y > m)
{
cnt--;
return ;
}
else vis[a[x][y] - 'A'] = ;
dfs(x+ , y , cnt+);
dfs(x- , y , cnt+);
dfs(x , y+ , cnt+);
dfs(x , y- , cnt+);
ans = max(cnt , ans);
vis[a[x][y] - 'A'] = ;//每一条走到最后的路径都互不影响,所以要取消标记。
} int main()
{
while(~scanf("%d%d" , &n , &m))
{
for(int i = ; i <= n ; i++)
{
for(int j = ; j <= m ; j++)
{
cin >> a[i][j];
}
}
ans = -INF ;
memset(vis , , sizeof(vis));
dfs( , , );
cout << ans << endl ;
} return ;
}
最新文章
- wordpress multisite functions
- MySQL服务 - 客户端工具mysql及mysqladmin使用介绍
- UDP及其组播,接收发送封装
- oracle 分区表的维护
- C++求等比数列之和
- Codeforces 14D
- 配置mybatis错误总结
- Visual Studio Installer打包后生成的安装文件每次执行都需要重新安装C++ 2010运行库(x86)的解决方案
- python+NLTK 自然语言学习处理:环境搭建
- require、缓存
- Android Studio代码行数统计插件Statistics
- SQL反模式学习笔记17 全文搜索
- IDEA使用SpringBoot 、maven创建微服务的简单过程
- JavaSE之概述
- 12月12日 has_many through:的interference, option
- mybatis逆向文件
- 以log(n)的时间求矩形内的点
- 学习python第一天 pycharm设置
- C#高级参数ref的使用
- iOS实时监控网络状态的改变