1、LA 3977 Summits
题意：如果一点是山顶的话，其走高度大于h-d的地形不能到达另外一个比其高的地方。问有多少个d型山顶。
思路：按照高度从高到低BFS：
①如果该点高度大于h-d并且没有访问过，则压入。
②如果该点大于h-d并且有更高的地形能够BFS到达这里，则说明此次BFS到的所有的点都能走一条h-d的路径到大于其高度的地形。
③如果不满足条件②，则说明此次BFS不能到达高度大于BFS的源点高度，则计数器加上此次BFS中可以到达的高度和源点相同的点的数目(包含源点)。
1 //题意：如果一点是山顶的话，其走高度大于h-d的地形不能到达另外一个比其高的地方。 2 #include3 #include 4 #include 5 #include 6 using namespace std; 7 const int maxr = 510; 8 const int maxc = 510; 9 int h, w, d;10 int mp[maxr][maxc];11 int vis[maxr][maxc];12 int cnt;13 struct point14 {15 int x;16 int y;17 int h;18 point(int xx=0,int yy=0,int hh=0):x(xx),y(yy),h(hh){ }19 friend bool operator <(const point&a, const point&b)20 {21 return a.h > b.h;22 }23 }tot[maxr*maxc];24 int dr[] = { 0,0,1,-1 };25 int dc[] = { 1,-1,0,0 };26 void BFS(int x, int y)27 {28 queue q;29 q.push(point(x, y, mp[x][y]));30 vis[x][y] = mp[x][y];31 bool flag = true;32 int count=1;33 while (!q.empty())34 {35 point u = q.front();36 q.pop();37 for (int i = 0; i < 4; i++)38 {39 int dx = u.x + dr[i];40 int dy = u.y + dc[i];41 if (dx >= 0 && dx < h&&dy >= 0 && dy < w)42 {43 if (u.h - d < mp[dx][dy])44 {45 if (vis[dx][dy] == -1)46 {47 q.push(point(dx, dy, u.h));48 vis[dx][dy] = u.h;49 if (mp[dx][dy] == u.h) count++;50 }51 else if (vis[dx][dy] > u.h) flag = false;52 }53 }54 }55 }56 if (flag) cnt+=count;57 }58 void Solve()59 {60 sort(tot, tot + h*w);61 for (int i = 0; i < h*w; i++)62 {63 int x = tot[i].x;64 int y = tot[i].y;65 if (vis[x][y] == -1) BFS(x, y);//如果是已访问的点，则其必能到达一个高度大于66 }67 printf("%d\n", cnt);68 }69 int main()70 {71 int t;72 scanf("%d", &t);73 while (t--)74 {75 scanf("%d%d%d", &h, &w, &d);76 cnt = 0;77 for (int i = 0; i < h; i++)78 {79 for (int j = 0; j < w; j++)80 {81 scanf("%d", &mp[i][j]);82 vis[i][j] = -1;83 tot[i*w + j] = point(i, j, mp[i][j]);84 }85 }86 Solve();87 }88 return 0;89 }