題意是給出一個(gè)矩陣中點(diǎn)的坐標(biāo)，求網(wǎng)格圖中的連通分量，這類題目很多了，只不過這道題要使用hash或者平衡樹來判斷點(diǎn)是否存在。
有件及其汗顏的事情，我用自己寫的hash竟然超時(shí)，然后用STL SET水過去了，無語
1 # include <iostream>
2 # include <cstdio>
3 # include <set>
4 using namespace std;
5 class node
6 {
7 public:
8 int r,c,val;
9 node(int rr,int cc,int vv):r(rr),c(cc),val(vv){};
10 };
11 struct cmp
12 {
13 bool operator()(const node &a,const node &b) const
14 {
15 if(a.r!=b.r) return a.r<b.r;
16 else return a.c<b.c;
17 }
18 };
19 set<node,cmp> refer;
20 int solve(node pos)
21 {
22 set<node,cmp>::iterator p=refer.find(pos);
23 if(p==refer.end()) return 0;
24 else
25 {
26 int val=p->val;
27 refer.erase(p);
28 return solve(node(pos.r+1,pos.c,pos.val))+solve(node(pos.r-1,pos.c,pos.val))+solve(node(pos.r,pos.c+1,pos.val))+solve(node(pos.r,pos.c-1,pos.val))+val;
29 }
30 }
31 int main()
32 {
33 int n;
34 while(true)
35 {
36 scanf("%d",&n);
37 if(!n) break;
38 while(n--)
39 {
40 int r,c,v;
41 scanf("%d%d%d",&r,&c,&v);
42 refer.insert(node(r,c,v));
43 }
44 int res=0;
45 while(!refer.empty())
46 {
47 int ans=solve(*(refer.begin()));
48 if(ans>res) res=ans;
49 }
50 printf("%d\n",res);
51 }
52 return 0;
53 }
54