文章目录

• • Luogu - [P1434 [SHOI2002]滑雪](https://www.luogu.com.cn/problem/P1434)
  • Luogu - [P1101 单词方阵](https://www.luogu.com.cn/problem/P1101)

Luogu - P1434 [SHOI2002]滑雪

题目描述
Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：

1   2   3   4   5
16  17  18  19   6
15  24  25  20   7
14  23  22  21   8
13  12  11  10   9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可行的滑坡为24－17－16－1（从24开始，在1结束）。当然25－24－23－…－3－2－1更长。事实上，这是最长的一条。

记忆化搜索

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310;
int g[N][N];
int f[N][N];
int n, m;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dfs(int x, int y)
{
    int &v = f[x][y];
    if (v != -1) return v;
    
    v = 1;
    for (int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        if (g[x][y] > g[a][b]) 
            v = max(v, 1 + dfs(a, b));
    }
    
    return v;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ ) scanf("%d", &g[i][j]);
    
    memset(f, -1, sizeof f);
    
    int ans = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ ) 
            ans = max(ans, dfs(i, j));
    
    cout << ans;
    return 0;
}

Luogu - P1101 单词方阵

深搜染色

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;

int n;
string s = "yizhong";
char g[N][N];
int st[N][N];
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};


void dfs(int x, int y, int dir) 
{
    int a = x, b = y;
    for (int i = 0; i < 7; i++)
    {
        if (g[a][b] != s[i]) return;
        a = a + dx[dir];
        b = b + dy[dir];
    }
    
    a = x, b = y;
    for (int i = 0; i < 7; i++)
    {
        st[a][b] = true;
        a = a + dx[dir];
        b = b + dy[dir];
    }
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
	    for (int j = 1; j <= n; j++)
	        cin >> g[i][j];
	   
	for (int i = 1; i <= n; i++)
	    for (int j = 1; j <= n; j++)
	        if (g[i][j] == 'y')
	            for (int k = 0; k < 8; k++) 
	                dfs(i, j, k);
	                
	for (int i = 1; i <= n; i++)
	{
	    for (int j = 1; j <= n; j++)
	        if (st[i][j]) cout << g[i][j];
	        else cout << "*";
	    cout << endl;       
	}
	  
	return 0;
}