90分#6WA，求助

_NOCl_ @ 2023-09-02 14:24:14

#include<iostream>
#include<algorithm>
using namespace std;
int rows, cols;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int squ[101][101] = { {0} };
int store[101][101] = { {0} };

int dfs(int x, int y) {
    if (store[x][y] != 0) return store[x][y];
    for (int i = 0; i < 4; i++) {
        int tx = x + dx[i];
        int ty = y + dy[i]; 
        if (tx >= 0 && ty >= 0 && tx <= cols && ty <= rows) {
            if (squ[x][y] > squ[tx][ty]) {              
                dfs(tx, ty);
                store[x][y] = max(store[x][y], store[tx][ty] + 1);
            }
        }       
    }
    return store[x][y];
}
int main() {
    cin >> rows >> cols;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            cin >> squ[i][j];
        }
    }
    int ans = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            ans = max(dfs(i, j), ans);      
        }       
    }
    cout << ans + 1;
}

by BugGod @ 2023-09-02 14:35:32

@NOCl

#include<iostream>
#include<algorithm>
using namespace std;
int rows, cols;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int squ[101][101] = { {0} };
int store[101][101] = { {0} };

int dfs(int x, int y) {
    if (store[x][y] != 0) return store[x][y];
store[x][y]=1;
    for (int i = 0; i < 4; i++) {
        int tx = x + dx[i];
        int ty = y + dy[i]; 
        if (tx >= 0 && ty >= 0 && tx < rows && ty < cols) {
            if (squ[x][y] > squ[tx][ty]) {              
                dfs(tx, ty);
                store[x][y] = max(store[x][y], store[tx][ty] + 1);
            }
        }       
    }
    return store[x][y];
}
int main() {
    cin >> rows >> cols;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            cin >> squ[i][j];
        }
    }
    int ans = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            ans = max(dfs(i, j), ans);      
        }       
    }
    cout << ans ;
}

by BugGod @ 2023-09-02 14:37:29

@NOCl 你的dfs判断里r和c写反了，而且你下标从0开始，应该是小于而不是小于等于

by _NOCl_ @ 2023-09-02 14:40:23

@Quantum_Graph 谢谢帮助，但是这个是范围问题，

store[x][y]//记忆化搜索，而不是判断是否使用过

改变了一下搜索的范围

#include<iostream>
#include<algorithm>
using namespace std;
int rows, cols;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int squ[105][105] = { {0} };
int store[105][105] = { {0} };

int dfs(int x, int y) {
    if (store[x][y] != 0) return store[x][y];
    for (int i = 0; i < 4; i++) {
        int tx = x + dx[i];
        int ty = y + dy[i]; 
        if (tx > 0 && ty > 0 && tx <= rows && ty <= cols) {
            if (squ[x][y] > squ[tx][ty]) {      
                dfs(tx, ty);
                store[x][y] = max(store[x][y], store[tx][ty] + 1);
            }
        }       
    }
    return store[x][y];
}
int main() {
    cin >> rows >> cols;
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            cin >> squ[i][j];
        }
    }
    int ans = 0;
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            ans = max(dfs(i, j), ans);      
        }       
    }
    cout << ans + 1;
}

这下AC过了

by BugGod @ 2023-09-02 14:44:42

@NOCl 不是，我的写法是把 s[x][y] 记为1（自己走向自己算一步）

by BugGod @ 2023-09-02 14:45:29

@Quantum_Graph 而不是像你一样，最后加一步。