1 #include<iostream>
2 #include<algorithm>
3 #include<cstring>
4 #include<fstream>
5 using namespace std;
6
7 int n, m;
8 int h[510][510];
9 int dx[4] = { -1,1,0,0 };
10 int dy[4] = { 0,0,1,-1 };
11 bool vis[510][510];
12
13 #define xx x+dx[i]
14 #define yy y+dy[i]
15
16 int l[510][510];
17 int r[510][510];
18
19 void dfs(int x, int y)
20 {
21 vis[x][y] = true;
22 for (int i = 0; i < 4; i++)
23 {
24 if (xx<1 || xx>n || yy<1 || yy>m) continue;
25 if (h[x][y] <= h[xx][yy]) continue;
26 if (!vis[xx][yy]) dfs(xx, yy);
27 l[x][y] = min(l[x][y], l[xx][yy]);
28 r[x][y] = max(r[x][y], r[xx][yy]);
29 }
30 }
31
32 int main()
33 {
34 ifstream fin("d:\\text.in");
35 //fin >> n >> m;
36 cin >> n >> m;
37 for (int i = 1; i <= n; i++)
38 {
39 for (int j = 1; j <= m; j++)
40 {
41 //fin >> h[i][j];
42 cin >> h[i][j];
43 }
44 }
45 memset(l, 0x3f, sizeof(l));
46 for (int i = 1; i <= m; i++)
47 {
48 l[n][i] = i;
49 r[n][i] = i;
50 }
51 for (int i = 1; i <= m; i++)
52 if (!vis[1][i]) dfs(1, i);
53 int cnt = 0;
54 for (int i = 1; i <= m; i++)
55 {
56 if (!vis[n][i]) cnt++;
57 }
58 if (cnt)
59 {
60 cout << 0 << endl;
61 cout << cnt;
62 }
63 else
64 {
65 int left = 1;
66 while (left <= m)
67 {
68 int maxr = 0;
69 for (int i = 1; i <= m; i++)
70 {
71 if (l[1][i] <= left)
72 {
73 maxr = max(maxr, r[1][i]);
74 }
75 }
76 cnt++;
77 left = maxr + 1;
78 }
79 cout << 1 << endl;
80 cout << cnt;
81 }
82 }
