욕심쟁이 판다

*현재 좌표는 항상 1일 (dp[][]을 1로 초기화한다)

*현재 좌표에서 최대한 많이 갈 수 있는 날을 dp[][] 에 저장한다. 

 

#include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; int n; int map[501][501]; int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 }; typedef pair<int, int> pp; typedef pair<int, pp> ipp; int dp[501][501]; bool visited[501][501]; int dfs(int x, int y) { if (dp[x][y] != 1) return dp[x][y]; int &ret = dp[x][y]; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= n ) continue; if (map[nx][ny] > map[x][y]) { ret = max(ret, dfs(nx, ny) + 1); } } return ret; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; vector<ipp> v; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> map[i][j]; //v.push_back(ipp(map[i][j], pp(i, j))); dp[i][j] = 1; //자기자신은 1일 } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dp[i][j] = dfs(i, j); } } int max = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { max = max > dp[i][j] ? max : dp[i][j]; } } cout << max << '\n'; return 0; }