HackerEarth Inverted cells problem solution

In this HackerEarth Inverted cells problem solution You are given a matrix n * m. The matrix rows are numbered from 1 to n from top to bottom and the matrix columns are numbered from 1 to n from left to right. The cells of the field at the intersection of the xth row and the yth column has coordinates (x,y).

Every cell is empty or blocked. For every cell (x,y), determine if you change the state of cell (x,y)(empty to blocked or blocked to empty), then is it possible to reach cell (n,m) from (1,1) by going only down and right.

HackerEarth Inverted cells problem solution.

#include <bits/stdc++.h>
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ll long long
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define VAR(v, i) __typeof( i) v=(i)
#define forit(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
 
using namespace std;
 
const int maxn = (int)2e3 + 100;
const int mod = (int)1e9 + 7;
const int P = (int) 1e6 + 7; 
const double pi = acos(-1.0);
 
#define inf mod
 
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;   
typedef vector<ll> Vll;               
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;                        
    

int n, m, cnt[maxn];
char s[maxn][maxn];
bool can1[maxn][maxn], can2[maxn][maxn], good[maxn][maxn];
int main () {
    scanf("%d%d\n", &n, &m);
    forn(i, 1, n)
        scanf("%s", s[i] + 1);
    can1[1][1] = 1;
    forn(i, 1, n)
        forn(j, 1, m)
            if(s[i][j] == '.')
                can1[i][j] |= (can1[i][j - 1] | can1[i - 1][j]);
    can2[n][m] = 1;
    forev(i, n, 1)
        forev(j, m, 1)
            if(s[i][j] == '.')
                can2[i][j] |= (can2[i][j + 1] | can2[i + 1][j]);
    forn(i, 1, n)
        forn(j, 1, m)
            good[i][j] = (can1[i][j] & can2[i][j]), cnt[i + j] += good[i][j];
    forn(i, 1, n){
        forn(j, 1, m){
            if(s[i][j] == '#'){
                if(can1[n][m]) printf("1 ");
                else{
                    int ok1 = 0, ok2 = 0;
                    if(i > 1) ok1 |= can1[i - 1][j];
                    if(j > 1) ok1 |= can1[i][j - 1];
                    if(i < n) ok2 |= can2[i + 1][j];
                    if(j < m) ok2 |= can2[i][j + 1];
                    printf("%d ", (ok1 & ok2));
                }
            }
            else{
                if(!can1[n][m]){
                    printf("0 ");
                    continue;
                }
                if(good[i][j] && cnt[i + j] == 1) printf("0 ");
                else printf("1 ");
            }
        }
        puts("");
    }
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e3 + 4;
int n, m;
bool ok[maxn][maxn], a[maxn][maxn], b[maxn][maxn], ff[maxn][maxn];
char c[maxn][maxn];
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        cin >> c[i];
    for(int i = n - 1; i >= 0; i--)
        for(int j = m - 1; j >= 0; j--)
            ok[i][j] = c[i][j] == '.' && (i == n - 1 && j == m - 1 || ok[i + 1][j] || ok[i][j + 1]);
    if(!ok[0][0]){
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                ff[i][j] = c[i][j] == '.' && (i == 0 && j == 0 || i && ff[i - 1][j] || j && ff[i][j - 1]);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++)
                cout << ((j && ff[i][j - 1] || i && ff[i - 1][j]) && (ok[i + 1][j] || ok[i][j + 1])) << ' ';
            cout << '\n';
        }
        return 0;
    }
    // for(int i = 0; i < n; i++)
    //     for(int j = 0; j < m; j++)
    //             cerr << ok[i][j] << " \n"[j == m - 1];
    int x = 0, y = 0;
    bool allz = false;
    while(x != n - 1 || y != m - 1){
        a[x][y] = true;
        if(ok[x + 1][y])
            x++;
        else if(ok[x][y + 1])
            y++;
        else{
            allz = true;
            break;
        }
    }
    a[x][y] = true;
    x = y = 0;
    while(x != n - 1 || y != m - 1){
        b[x][y] = true;
        if(ok[x][y + 1])
            y++;
        else if(ok[x + 1][y])
            x++;
        else{
            allz = true;
            break;
        }
    }
    b[x][y] = true;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++)
            cout << !(allz || a[i][j] && b[i][j]) << ' ';
        cout << '\n';
    }
}