P1514 引水入城

 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 }