سلام
امروز یک مسئله خوب ACM به نام حل مسئله محیط تصاویر Image Perimeters Solotion را برای حل انتخاب کرده ایم این سوال را با استفاده از توابع بازگشتی حل کرده ایم.
این مسئله از مسابقه Mid-Central USA 2001 انتخاب شده است
لینک سوال در ICPC Live Archive
لینک سوال در ShareCode.ir

حل مسئله محیط تصاویر Image Perimeters Solotion
خب قبل اینکه ادامه مطلب را بخوانید ابتدا متن سوال را مطالعه فرماید و سعی کنید که خودتان حل کنید .


یک توضیح کلی در مورد سوال می دهم یک صفحه از Character  داریم که متشکل از '.'  یا 'X' هستند 'X' های بهم چسبیده یک شکل را ایجاد میکنند کاربر مختصات هر نقطه ای را که داد برنامه ما باید مساحت دور این شکل را به خروجی ارسال کند .
خب برای این کار من یک تابع به اسم hcounting(int u,int v) نوشتم که این تابع وظیفه پیمایش در این شکل را دارد و هنگامی که به گوشه ها رسید مقدار count که همان مساحت ماست را زیاد میکند
خب سوال این است که چگونه در این شکل پیمایش میکند در واقع این تابع اگر برای 'X' های کنج ها صدا زده شده باشد مقدار count را اضافه میکند ... و در هر صورت 'X'  های مجاورش را صدا میزند.
خب حالا فرض کنید ما دو 'X' کنار هم داریم
اولی دومی را صدا میزند
دومی اولی را صدا میزند و باز اولی دومی را صدا میزند و این روند بی نهایت بار تکرار می شود
برای اینکه یک 'X' دوبار صدا زده نشود ما یک ارایه  دو بعدی به اسم visited با مقدار صفر بطور پیشفرض در نظر گرفته ایم که اگر  'X' صدا زده شده باشد خانه نظیر این  'X' درون آرایه دو بعدی مقدار یک میگیرد ... و هنگام صدا زدن توجه میکنیم که visited خانه ای که میخواهیم صدا بزنیم 0 باشد.
خب وقتی تمامی خانه ها صدا زده شده اند تابع بازگشتی متوقف میشود و مقدار count همان مساحت دور شکل میباشد

منتظر نظرات شما دوستان هستم .

#include<iostream>

#include<string>

using namespace std;

int count,n,m;

int visited[25][25];

string board[25];

int ip[8]={0,1,0 ,-1,1,-1,-1, 1};

int jp[8]={1,0,-1, 0,1,-1, 1,-1};

int hcounting(int u,int v){

       visited[u][v]=1;

       int i;

       for(i=0;i<4;i++){

              if(u+jp[i]==n||u+jp[i]<0)count++;

              else if(v+ip[i]==m||v+ip[i]<0)count++;

              else if(board[u+jp[i]][v+ip[i]]=='.')count++;

       }

       for(i=0;i<8;i++){

              if(u+jp[i]>=n||u+jp[i]<0)continue;

              if(v+ip[i]>=m||v+ip[i]<0)continue;

              if(board[u+jp[i]][v+ip[i]]=='X'&&!visited[u+jp[i]][v+ip[i]]){

                     hcounting(u+jp[i],v+ip[i]);

              }

       }

       return 0;

}



int main(){

       int i,j,u,v;

       while(cin>>n>>m>>u>>v&&n){

              for(i=0;i<25;i++)

                     for(j=0;j<25;j++)

                           visited[j][i]=0;

              for(i=0;i<n;i++)

                     cin>>board[i];

              count=0;

              hcounting(u-1,v-1);

              cout<<count<<"\n";

       }

}