[UVa] 10336 - Rank the Languages

題目網址:  https://goo.gl/W5RSgj

題意:
(from luckycat)


解法:
直接DFS每個符號，算有幾個不相連的區域，排序大小。

TAG: DFS

注意:

程式碼:

	/**
	* Tittle: 10336 - Rank the Languages
	* Author: Cheng-Shih, Wong
	* Date: 2015/06/29
	*/
	// include files
	#include <bits/stdc++.h>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 1005
	typedef pair<int,char> PIC;
	typedef vector<PIC> VPIC;
	// declarations
	int n;
	int h, w;
	char m[N][N];
	bool vis[N][N];
	int cnt[30];
	// functions
	void input( void )
	{
	scanf( "%d%d", &h, &w );
	FOR( i, 1, h )
	scanf( "%s", m[i]+1 );
	}
	const bool cmp( const PIC &a, const PIC &b )
	{
	if( a.first != b.first ) return a.first > b.first;
	return a.second < b.second;
	}
	inline bool valid( int x, int y )
	{
	return (1<=x && x<=h && 1<=y && y<=w);
	}
	void dfs( int x, int y )
	{
	if( !valid(x,y) || vis[x][y] ) return;
	vis[x][y] = true;
	if( m[x+1][y]==m[x][y] ) dfs( x+1, y );
	if( m[x-1][y]==m[x][y] ) dfs( x-1, y );
	if( m[x][y+1]==m[x][y] ) dfs( x, y+1 );
	if( m[x][y-1]==m[x][y] ) dfs( x, y-1 );
	}
	void solve( void )
	{
	clr( cnt, 0 );
	clr( vis, false );
	FOR( i, 1, h ) FOR( j, 1, w ) if( !vis[i][j] ) {
	++cnt[m[i][j]-'a'];
	dfs(i,j);
	}
	VPIC arr;
	FOR( i, 0, 25 ) if( cnt[i] )
	arr.push_back( PIC(cnt[i],'a'+i) );
	sort( arr.begin(), arr.end(), cmp );
	for( PIC obj:arr )
	printf( "%c: %d\n", obj.second, obj.first );
	}
	// main function
	int main( void )
	{
	// input
	scanf( "%d", &n );
	FOR( ti, 1, n ) {
	printf( "World #%d\n", ti );
	input();
	solve();
	}
	return 0;
	}

view raw 10336 - Rank the Languages.cpp hosted with ❤ by GitHub