- আমরা আমাদের আইল্যান্ড থেকে একটা করে পজিশন রিড করবো । যদি ' . ' পাই তবে সেটা স্কিপ করবে ।
- এখন প্রত্যেক টা গর্তের জন্য সেখানে Flood Fill চালাবো । আমাদের কে পাশাপাশি ৪ দিকে যেতে হবে এবং হিসাব করতে হবে ওই একই ধরনের ক্যারেক্টার আসে পাশে কয়টা আছে ।
- ওই ক্যারেক্টার ছাড়া অন্য কোন ক্যারেক্টার পাই তবে আমাদের কে সেখান থেকে ব্যাক করতে হবে ।
- একই ধরনের কয়টা ক্যারেক্টার পাওয়া গেলও সেটা আমাদের rank_list এ ওই ক্যারেক্টার সহ জমা করে রাখতে হবে ।
- পুরা আইল্যান্ড যখন ভ্রমণ করা শেষ তখন আমাদের rank_list কে সমস্যা তে বর্ণিত শর্ত অনুসারে সর্ট করতে হবে ।
- rank_list এর সাইজ ৫০ * ৫০ এর একটু বেশি করে রাখা নিরাপদ ।
- কারণ আমাদের আইল্যান্ড এর প্রত্যেক টা পজিশন যদি আলাদা আলাদা হোল হয় সেই ক্ষেত্রে যদি rank_list এর সাইজ ছোট হয় তবে রানটাইম এরর খেতে হবে :)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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; | |
} |
হ্যাপি কোডিং :)
Comments
Post a Comment