原题传送门:http://poj.org/problem?id=3620
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 6211 | Accepted: 3370 |
Description
Farmer John's farm was flooded in the most recent storm, a fact only aggravated by the information that his cows are deathly afraid of water. His insurance agency will only repay him, however, an amount depending on the size of the largest "lake" on his farm.
The farm is represented as a rectangular grid with N (1 ≤ N ≤ 100) rows and M (1 ≤ M ≤ 100) columns. Each cell in the grid is either dry or submerged, and exactly K (1 ≤ K ≤ N × M) of the cells are submerged. As one would expect, a lake has a central cell to which other cells connect by sharing a long edge (not a corner). Any cell that shares a long edge with the central cell or shares a long edge with any connected cell becomes a connected cell and is part of the lake.
Input
* Line 1: Three space-separated integers: N, M, and K
* Lines 2..K+1: Line i+1 describes one submerged location with two space separated integers that are its row and column: R and C
Output
* Line 1: The number of cells that the largest lake contains.
Sample Input
3 4 5 3 2 2 2 3 1 2 3 1 1
Sample Output
4
Source
//深度优先遍历 DFS POJ 3602 #include<stdio.h> #include<stack> #include<string.h> #include<cmath> using namespace std; int N,M,K,a,b; const int MAXN = 110; int form[MAXN][MAXN]; bool visit[MAXN][MAXN]; int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; int count; int ans; void DFS(int x,int y){ int xx,yy; for(int i=0;i<4;i++){ xx = x + dir[i][0]; yy = y + dir[i][1]; if(xx<1||yy<1||xx>N||yy>M) continue; if(form[xx][yy] && !visit[xx][yy]){ count++; visit[xx][yy] = 1; DFS(xx,yy); } } } int main(){ while(scanf("%d%d%d",&N,&M,&K)==3){ ans = 0; memset(form,0,sizeof(form)); memset(form,false,sizeof(visit)); while(K--){ scanf("%d%d",&a,&b); form[a][b] = 1; } for(int i=1;i<=N;i++){ for(int j=1;j<=M;j++){ if(form[i][j]&&!visit[i][j]){ count = 1; visit[i][j]=1; DFS(i,j); ans = max(ans,count); } } } printf("%d\n",ans); } return 0; }
相关推荐
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ1027-The Same Game 解题报告+AC代码
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1163-The Triangle
POJ2635-The Embarrassed Cryptographer 测试数据。 来源:NCPC 2005 问题D
北大POJ3267-The Cow Lexicon
北大POJ2635-The Embarrassed Cryptographer 解题报告+AC代码
北大POJ2965-The Pilots Brothers' refrigerator 解题报告+AC代码
北大POJ3982-The Fibonacci sequence 解题报告+AC代码
北大POJ3267-The Cow Lexicon 解题报告+AC代码
poj 3548 Restoring the digits.md
poj 1611 The Suspects 代码 并查集的应用
poj 3554 Almost the shortest route.md
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
北大POJ2151-Check the difficulty of problems 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ2983-Is the Information Reliable【差分约束+优化Bellman】 解题报告+AC代码
北大POJ3239-Solution to the n Queens Puzzle 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj 1611 The Suspects.md