UVA 11624 - Fire!

UVA Sep 1, 2020

Problem PDF

Solution:

/******************************************************************
***   Problem       :                                           ***
***   Author        : Shipu Ahamed (Psycho Timekiller)          ***
***   E-mail        : [email protected]                   ***
***   University    : BUBT,Dept. of CSE                         ***
***   Team          : BUBT_Psycho                               ***
***   My Blog       : http://shipuahamed.blogspot.com           ***
***   Facebook      : http://www.facebook.com/DeesheharaShipu   ***
******************************************************************/

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define pi 2*acos(0.0)
#define all(v) v.begin(),v.end()
#define coff ios_base::sync_with_stdio(0);

#define ff first
#define se second
#define pb push_back
#define sz(a) ((int)a.size())
#define ST(v) sort(all(v))
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define maxall(v) *max_element(all(v))
#define minall(v) *min_element(all(v))
#define cover(a,d) memset(a,d,sizeof(a))
#define popcount(i) __builtin_popcount(i)      //count one. in long long use __builtin_popcountll(i)
#define parity(i)   __builtin_parity(i)       //evenparity 0 and odd parity 1
#define btz(a)   __builtin_ctz(a)            //count binary trailling zero
#define un(v) ST(v), (v).erase(unique(all(v)),v.end())
#define common(a,b) ST(a), ST(b), a.erase(set_intersection(all(a),all(b),a.begin()),a.end())
#define uncommon(a,b) ST(a), ST(b), a.erase(set_symmetric_difference(all(a),all(b),a.begin()),a.end())

typedef  long long ll;
typedef  unsigned long long ull;

template string toString( T Number ){stringstream st;st << Number;return st.str();}
int stringconvert(string s){int p; istringstream st(s); st>>p ; return p;}

//upper bound and lower bound
#define LB(a,value) (lower_bound(all(a),value)-a.begin())
#define UB(a,value) (upper_bound(all(a),value)-a.begin())

//Debug
#define dbg(x) cout<<#x<<'='<>= 1; } return res; }
ll modInverse(ll a, ll m){return bigmod(a,m-2,m);}

////============ CONSTANT ===============////
#define inf   INT_MAX                                           //infinity value
#define eps   1e-9
#define mx    100010
#define mod   1000000007
////=====================================////


int row,col;

struct info
{
    int x,y;
    info(int xx,int yy)
    {
        x=xx;
        y=yy;
    }
    info(){}
};

int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

int in_grid(int i,int j)
{
    if((i >= 0 && i < row) && (j >= 0 && j < col))
    {
        return 1;
    }
    else
        return 0;
}


int jan[1010][1010],f[1010][1010];
bool vis[1010][1010];
char grid[1010][1010];

int bfs(info n)
{
    cover(vis,0);

    queueq;
    q.push(n);

    jan[n.x][n.y]=0;

    while(!q.empty())
    {
        info p=q.front();
        q.pop();

        for(int i=0;i<4;i++)
        {
            int x=p.x+dx[i];
            int y=p.y+dy[i];

            if(!in_grid(x,y))
                continue;

            if(!vis[x][y] && grid[x][y]=='.')
            {
                if(jan[p.x][p.y]==inf)
                    jan[p.x][p.y]=0;
                jan[x][y]=jan[p.x][p.y]+1;
                vis[x][y]=1;
                q.push(info(x,y));
            }
        }
    }

    cover(vis,0);

    vectorfire;
    for(int i=0;i
https://github.com/Shipu/OnlineJudgeProblemSolutionWithCPlusPlus/tree/master/uva/11624/11624.cpp

Tags

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.