[ UVa ] 10946 - You want what filled ?

• আমরা আমাদের আইল্যান্ড থেকে একটা করে পজিশন রিড করবো । যদি ' . ' পাই তবে সেটা স্কিপ করবে । 
• এখন প্রত্যেক টা গর্তের জন্য সেখানে Flood Fill চালাবো । আমাদের কে  পাশাপাশি ৪ দিকে যেতে হবে এবং  হিসাব করতে হবে  ওই একই ধরনের ক্যারেক্টার আসে পাশে কয়টা আছে ।  
• ওই ক্যারেক্টার ছাড়া অন্য  কোন ক্যারেক্টার পাই তবে আমাদের কে সেখান থেকে ব্যাক করতে হবে । 
• একই ধরনের কয়টা ক্যারেক্টার পাওয়া গেলও সেটা আমাদের rank_list এ ওই ক্যারেক্টার সহ জমা করে রাখতে হবে । 
• পুরা আইল্যান্ড যখন ভ্রমণ করা শেষ তখন আমাদের  rank_list কে সমস্যা তে বর্ণিত শর্ত অনুসারে সর্ট করতে হবে । 
• rank_list এর সাইজ ৫০ * ৫০ এর একটু বেশি করে রাখা নিরাপদ । 
•  কারণ আমাদের আইল্যান্ড এর প্রত্যেক টা পজিশন যদি আলাদা আলাদা হোল হয় সেই ক্ষেত্রে যদি rank_list এর সাইজ ছোট হয় তবে রানটাইম এরর খেতে হবে :) 

কোড :

	/**
	* Problem : 10946 - You want what filled?
	* Verdict : Accepted.
	* Writer : Mehadi Hasan Menon.
	* Date : 25.12.16.
	**/
	#include <iostream>
	#include <algorithm>
	#include <cstdio>
	using namespace std;
	const int mx = 55;
	char island[mx][mx];
	int x, y;
	int dr[] = {-1, 0, 1, 0};
	int dc[] = {0, 1, 0, -1};
	struct data
	{
	int rank_size;
	char name;
	} rank_list[2505];
	// max different hole may be 50 x 50
	// this will will skip run time ERROR :)
	bool compare(const data &a, const data &b)
	{
	if(a.rank_size == b.rank_size)
	{
	return a.name < b.name;
	}
	else
	{
	return a.rank_size > b.rank_size;
	}
	}
	int dfs(int r, int c, char new_hole)
	{
	if(r < 0 || r >= x || c < 0 || c >= y || island[r][c] != new_hole)
	{
	return 0;
	}
	if(island[r][c] == '.')
	{
	return 0;
	}
	island[r][c] = '.';
	int ans = 1;
	for(int i = 0; i < 4; i++)
	{
	int new_row = r + dr[i];
	int new_col = c + dc[i];
	ans += dfs(new_row, new_col, new_hole);
	}
	return ans;
	}
	int main()
	{
	freopen("input.txt", "r+", stdin);
	int tc = 1;
	while(scanf("%d %d", &x, &y) && x != 0 && y != 0)
	{
	for(int i = 0; i < x; i++)
	{
	scanf("%s", island[i]);
	}
	int index = 0;
	for(int i = 0; i < x; i++)
	{
	for(int j = 0; j < y; j++)
	{
	if(island[i][j] != '.')
	{
	rank_list[index].name = island[i][j];
	rank_list[index].rank_size = dfs(i, j, island[i][j]);
	index += 1;
	}
	}
	}
	// sort our rank list structure
	sort(rank_list, rank_list + 2505, compare);
	// finally print result
	printf("Problem %d:\n", tc);
	for(int i = 0; i < 2505; i++)
	{
	if(rank_list[i].rank_size == 0)
	{
	break;
	}
	printf("%c %d\n", rank_list[i].name, rank_list[i].rank_size);
	}
	tc += 1;
	// reset our rank list
	for(int i = 0; i < 2505; i++)
	{
	rank_list[i].rank_size = 0;
	}
	}
	return 0;
	}

view raw 10946.cpp hosted with ❤ by GitHub

হ্যাপি কোডিং :)