Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Floodfil 235 MS

Posted by __ea at 2016-11-12 14:55:35 on Problem 2375 and last updated at 2016-11-12 14:57:40
Solution: Notice that the grid given can be made into a graph. 
          Compress each strongly connected component into a
          a vertex of that graph. Notice that a strongly connected
          component in this graph is just adjacent areas with the
          same height, and can be identified with flood fill. For
          each vertex of the new graph, find the number of indegree
          and outdegree edges. The vertices that are important are
          the ones with either zero indegree edges or zero outdegree
          edges. These vertices are the ones at the beginning or end
          of a path (you start there or you end up there). Make the 
          observation that the answer is the maximum of vertices with
          zero indegree edges and vertices with zero outdegree edges,
          since there is always some way to pair them up like that.

P.S: If you are using BFS as floodfill (like I did), do not put it
     in a separate function. Costed me multiple TLE's. TAT. Leaving
     the floodfill in the main function saves around 800 MS.

#include <iostream>
#include <cstdio>
#include <queue>
#include <list>
#include <cmath>
using namespace std;

const double Pi=acos(-1.0);
typedef long long LL;

#define Set(a, s) memset(a, s, sizeof (a))
#define Rd(r) freopen(r, "r", stdin)
#define Wt(w) freopen(w, "w", stdout)

typedef pair<int, int> point;
#define X first
#define Y second

#define MAX_R 501
#define MAX_C 501
int grid[MAX_R][MAX_C], vertex[MAX_R][MAX_C], R, C;
int indegree[MAX_R*MAX_C], outdegree[MAX_R*MAX_C];

int latestUse[MAX_R*MAX_C];

int main ()
{
	ios::sync_with_stdio(false);

	scanf("%d", &C);
	scanf("%d", &R);

	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++)
			scanf("%d", &grid[i][j]);

	queue<point>bfs;
	int nvertex = 0, dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (!vertex[i][j]) {
				int c = ++nvertex;
				point start = point(j, i);

				vertex[start.Y][start.X] = c;
				bfs.push(point(j, i));

				while(bfs.size()) {
					point curr = bfs.front(); bfs.pop();
					int currColor = grid[curr.Y][curr.X];

					for (int i = 0; i < 4; i++) {
						point nxt = point(curr.X+dir[i][0], curr.Y+dir[i][1]);

						if (nxt.X>=0 && nxt.X<C && nxt.Y>=0 && nxt.Y<R) {
							if (!vertex[nxt.Y][nxt.X] && grid[nxt.Y][nxt.X]==currColor)
								bfs.push(nxt), vertex[nxt.Y][nxt.X] = c;
							else if (vertex[nxt.Y][nxt.X] && latestUse[vertex[nxt.Y][nxt.X]]!=c) {
								if (grid[nxt.Y][nxt.X]<currColor)
									outdegree[c]++, indegree[vertex[nxt.Y][nxt.X]]++;
								else if (grid[nxt.Y][nxt.X]>currColor)
									indegree[c]++, outdegree[vertex[nxt.Y][nxt.X]]++;
								latestUse[vertex[nxt.Y][nxt.X]] = c;
							}
						}
					}
				}
			}
		}
	}



	int zeroin = 0, zerout = 0;
	for (int i = 1; i <= nvertex; i++)
		zeroin += (indegree[i]==0),
		zerout += (outdegree[i]==0);

	if (nvertex==1) zeroin=zerout=0;
	printf("%d\n", max(zeroin, zerout));


	return 0;
}



Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator