#include <bits/stdc++.h> using namespace std; int l[1000][1000] , a[1000][1000] , n , m; vector <pair<int , int>> kq; void qhd() { for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (a[i][j] == 1) l[i][j] = l[i - 1][j - 1] + 1; else l[i][j] = max(l[i - 1][j] , l[i][j - 1]); cout << l[n][m] << endl; int i = n , j = m; while ((i > 0) && (j > 0)) if (a[i][j] == 1) { kq.push_back({i , j}); i--; j--; } else if (l[i - 1][j] > l[i][j - 1]) i--; else j--; } int main() { freopen ("f.inp" , "r" , stdin); freopen ("f.out" , "w" , stdout); cin >> n >> m; int u , v; while (cin >> u >> v) { a[u][v] = 1; a[v][u] = 1; } qhd(); reverse (kq.begin() , kq.end()); for (auto x : kq) cout << x.first << " " << x.second << endl; return 0; }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter