Tags » BF's

11730 - Number Transformation

Problem Link

Same Problem : LightOJ

#Solution

#include<bits/stdc++.h>
using namespace std;
#define N 1010
int prime[N];
void sieve(){
bool notprime[N]={true,true};
for(int i=2;i<=50;i++)
for(int j=2*i;j<=N;j+=i)
notprime[j]=true;

127 more words

Breadth First Search

Template:

If a layer traversal is needed, add a “for” loop. (Attention that queue.size will change).

Java

UVa 469 - Wetlands of Florida

//aarifshuvo  ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

string sa;
bool vis;
int r , c;
int cnt = 0;

void dfs(int i, int j)
{
    if(i<0 or j<0 or i==r or j==c or vis[i][j]==1 or sa[i][j]=='L') return;

    vis[i][j] = 1;
    if(sa[i][j]=='W') cnt++;

    dfs(i+1,j+1);
    dfs(i+1,j-1);
    dfs(i-1,j+1);
    dfs(i-1,j-1);
    dfs(i,j+1);
    dfs(i,j-1);
    dfs(i+1,j);
    dfs(i-1,j);
}

int main()
{
    //freopen("F:/fout.txt", "w", stdout);
    int fl = 0;
    int t,i,j,idx=0;
    string s;
    scanf("%d", &t);
    getchar();
    getchar();
    while(t--)
    {
        if(fl==1) printf("\n"); fl = 1;
        r = 0, c = 0;
        idx = 0;

        while(getline(cin,s) and s!="")
        {
            if(s[0]=='W' or s[0]=='L')
            {
                sa = s;
                r = idx;
                c = SZ(s);
            }
            else
            {
                stringstream ss(s);
                ss >> i >> j;
                i--, j--;

                memset(vis,0,sizeof vis);

                if(sa[i][j]=='W' or sa[i][j]=='L')
                {
                    cnt = 0;
                    dfs(i,j);
                    printf("%d\n", cnt);
                }
            }
        }
    }

    return 0;
}
UVa

UVa 10004 - Bicoloring


///DFS SOLUTION
// aarifshuvo   ``CSEJU
#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

ll n,e,u,l,v;
vector<ll>adj;
int vis;
int col;

int dfs(int u)
{
    vis[u] = 1;

    REP(i,SZ(adj[u]))
    {
        int v = adj[u][i];

        if(!vis[v])

            col[v] = col[u]^1, dfs(v);

        else if(col[v]^col[u]==0) return 0;
    }

    return 1;
}


int main()
{
    while(scl(n) and n)
    {
        scl(l);

        REP(i,l) scll(u,v), adj[u].push_back(v), adj[v].push_back(u);

        if(dfs(0)) printf("BICOLORABLE.\n");
        else printf("NOT BICOLORABLE.\n");

        REP(i,209) adj[i].clear();
        memset(col,0,sizeof col);
        memset(vis,0,sizeof vis);
    }
    return 0;
}

----***---

///BFS SOLUTION: 
//aarifshuvo   ``CSEJU
#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

ll n,l,u,v;
vector<ll> adj;
ll col;

int bfs(int src)
{
    memset(col,-1,sizeof col);

    queue<ll> q;
    q.push(src);
    col=1;

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

        REP(i,SZ(adj[u]))
        {
            int v = adj[u][i];

            if(col[v]==-1)      // if adjacent is undiscovered
            {
                if(col[u]==1) col[v]=2;
                else if(col[u]==2) col[v]=1;

                q.push(v);
            }
            else
            {
                if(col[u]==col[v]) return 0;
            }
        }
    }
    return 1;
}

int main()
{
    while(scl(n) and n)
    {
        scl(l);

        REP(i,l) scll(u,v), adj[u].push_back(v), adj[v].push_back(u);

        if(bfs(0)) printf("BICOLORABLE.\n");
        else printf("NOT BICOLORABLE.\n");

        REP(i,209) adj[i].clear();
    }

    return 0;
}
UVa

STORYTIME: Does


STORYTIME: Does Penis Size Matter? My Bfs D*ck Is Too SMALL!
http://bit.ly/2jROZCo

[summary] Graph BFS solves problems

210: Course Schedule II
269: Alien Dictionary
题目描述见网站

210: 课程的dependency本来就存在edges数组表示,可以转换成map方便访问,然后对graph进行bfs
269: 从dict中抽出字母先后顺序,字母组成一个graph,对graph进行bfs

bfs的过程:

Queue先存入in degree为0的点
当queue不为空时:
取出点,加入结果
此点在map中指向的所有下一个点,给他们的in degree都减1
此时in degree为0的点重新加入queue

其实是有顺序的bfs,顺序为先访问dependency最小的点。这个方法两道题都可以解决。