题目描述
输入
输出
For each question, output the answer in one line.
样例输入
1 3 7 C 2 2 1 Q 2 2 C 1 2 2 Q 2 2 C 3 3 3 Q 3 3 Q 1 1
样例输出
1 2 3 -1
一看题目，想到的方法就是BFS，然后就写了，
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int maxn=1001; int group[maxn][maxn]; bool vis[maxn][maxn]; int dx[4]={0,0,1,-1}; int dy[4]={-1,1,0,0}; struct node { int x,y; }; queue<node>q; int main() { int t,MAX,a,b,v,n,m,mm; char str[2]; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); memset(group,0,sizeof(group)); mm=0; while(m--) { scanf("%s",str); if (str[0]==‘C‘) { scanf("%d%d%d",&a,&b,&v); group[a][b]=v; mm=max(mm,v); } else { scanf("%d%d",&a,&b); if (group[a][b]==0) printf("-1\n"); else { MAX=group[a][b]; if (mm==MAX) { printf("%d\n",mm); continue; } memset(vis,0,sizeof(vis)); node temp; temp.x=a; temp.y=b; vis[a][b]=true; q.push(temp); while(!q.empty()) { if (mm==MAX) { q.pop(); continue; } temp=q.front(); q.pop(); for (int i=0;i<4;i++) { int x=temp.x+dx[i]; int y=temp.y+dy[i]; if(!vis[x][y] && group[x][y]>0 && x>=1 && x<=n && y>=1 && y<=n) { vis[x][y]=true; MAX=max(MAX,group[x][y]); node temp1; temp1.x=x; temp1.y=y; q.push(temp1); } } } printf("%d\n",MAX); } } } } return 0; }
但是大家都知道，超时了，后来想了想，完全符合并查集的知识啊
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int maxn=2001; int n,m; struct node { int root,MAX; }p[maxn*maxn]; int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; int find(int x) { return p[x].root==x?x:p[x].root=find(p[x].root); } void init() { int nn=n*n; for (int i=0;i<=nn;i++) { p[i].root=i; p[i].MAX=0; } } int main() { int t,a,b,v; char str[2]; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); init(); while (m--) { scanf("%s",str); if (str[0]==‘C‘) { scanf("%d%d%d",&a,&b,&v); int temp2=find((a-1)*n+b); p[temp2].MAX=max(v,p[temp2].MAX); for (int i=0;i<4;i++) { int xx=a+dx[i]; int yy=b+dy[i]; if (xx>=1 && xx<=n && yy>=1 && yy<=n && p[find((xx-1)*n+yy)].MAX>0) { int temp1=find((xx-1)*n+yy); if (temp1!=temp2) p[temp1].root=p[temp2].root; p[temp2].MAX=max(p[temp1].MAX,p[temp2].MAX); } } } else { scanf("%d%d",&a,&b); int temp=find((a-1)*n+b); if (p[temp].MAX>0)printf("%d\n",p[temp].MAX); else printf("-1\n"); } } } return 0; }
hust 1625 Chessboard,布布扣,bubuko.com
原文：http://www.cnblogs.com/chensunrise/p/3732079.html