BFS

গুগ্লিং করেই BFS শিখে ফেলতে পারবে। তেমন কঠিন না। গুগ্লিং করার সময় BFS ppt  লিখে সার্চ দিলে power point এর স্লাইড আসবে। স্লাইড দিয়ে শেখাটা অনেক সহজ।

BFS from shafaetsplanet

#define MAX 1000

vector<int>con[MAX]; // graph representation
bool color[MAX];

void bfs(int start,int end)
{
    queue<int>Q;
    Q.push(start);
    color[start] = true;

    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();

        for(int i=0;i<con[u].size();i++)
        {
            int v = con[u][i];
            if(color[v] == false)
            {
                Q.push(v);
                color[v] = true;
            }
        }
    }

    return ; // return result
}

কিছু লজিকঃ

1. co-ordinate move এর ক্ষেত্রে manually move  গুলো না দিয়ে একটা array এর মধ্যে move গুলো রেখে সবগুলো move বের করা যায়।

int rrr[]={1,0,-1,0};
int ccc[]={0,1,0,-1};
// left, down, up, right

int x = 3,y = 5; // initial position

for(int i=0;i<4;i++)
{
    int u = x+rrr[i];
    int v = y+ccc[i];
    
    // u,v will contain new cordinate
}

Problem

UVA - 572, 469, 439, 532, 336, 260, 10004, 11080, 10336, 11518
Lightoj - 1012,1039
HDU - 4171