搜索与回溯算法:LETTERS

秒速五厘米 2024-04-19 08:34 4阅读 0赞

### 1212：LETTERS ###

时间限制: 1000 ms 内存限制: 65536 KB  
提交数: 9638 通过数: 4193

### 【题目描述】 ###

给出一个roe×colroe×col的大写字母矩阵，一开始的位置为左上角，你可以向上下左右四个方向移动，并且不能移向曾经经过的字母。问最多可以经过几个字母。

### 【输入】 ###

第一行，输入字母矩阵行数RR和列数SS，1≤R,S≤201≤R,S≤20。

接着输出RR行SS列字母矩阵。

### 【输出】 ###

最多能走过的不同字母的个数。

### 【输入样例】 ###

3 6
    HFDFFB
    AJHGDH
    DGAGEH

### 【输出样例】 ###

### 【来源】 ###

[No][]

> 求最大步数，可使用深度优先搜索进行遍历。

#include<iostream>
    #include<cstring>
    using namespace std;
    int fx[4] = {0,1,0,-1};
    int fy[4] = {-1,0,1,0};
    int ans = 0;
    int n,m;;
    char a[200][200];
    bool p[50000];
    int dfs(int x, int y, int z)
    {
    	ans = max(ans,z);
    	for(int i = 0; i < 4; ++i)
    	{
    		int xx = x+fx[i];
    		int yy = y+fy[i];
    		if(xx > 0 && xx <= n && yy > 0 && yy <= m && p[a[xx][yy]] == false)
    		//判断是否越界以及是否能走 
    		{
    			p[a[xx][yy]] = true;//标记走过的字母 
    			dfs(xx,yy,z+1);//以（xx,yy)继续搜索，走过的字母数+1 
    			p[a[xx][yy]] = false;//回溯法，退回上一步重新搜索方案 
    		}
    	}
    	return ans;
    }
    int main()
    {
    	//freopen("a.txt","r",stdin);
    	memset(p,false,sizeof(p));
    	cin >> n >> m;
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= m; ++j)
    		{
    			cin >> a[i][j];
    		}
    	}
    	p[a[1][1]] = true;//(1,1)记为已经走过，避免回到起点
    	dfs(1,1,1);//从（1,1）开始搜索，步数为1
    	cout << ans << endl;
    	return 0; 
    }

[No]: http://ybt.ssoier.cn:8088/problem_search.php?searchsource=No