Codeforces Round #641 (Div. 1) C

#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
using namespace std;
using ll = long long ;
const ll N = 1e3+10;
ll n,m,t;
char mp[N][N];
ll tim[N][N];
ll XX[5]= {0,0,1,-1};
ll YY[5]= {1,-1,0,0};
struct node
{
    ll X,Y,C;
};
queue<node>qq;
bool check(ll x,ll y)
{
    for(ll i=0; i<4; ++i)
    {
        if(x+XX[i]<0||x+XX[i]>=n||y+YY[i]<0||y+YY[i]>=m)
            continue;
        if(mp[x+XX[i]][y+YY[i]]==mp[x][y])
            return true;
    }
    return false;
}
void BFS()
{
    while(qq.size())
    {
        node k=qq.front();
        qq.pop();
        for(ll i=0; i<4; ++i)
        {
            if(k.X+XX[i]<0||k.X+XX[i]>=n||k.Y+YY[i]<0||k.Y+YY[i]>=m||tim[k.X+XX[i]][k.Y+YY[i]])
                continue;
            tim[k.X+XX[i]][k.Y+YY[i]]=k.C+1;
            node kk;
            kk.C=tim[k.X+XX[i]][k.Y+YY[i]];
            kk.X=k.X+XX[i];
            kk.Y=k.Y+YY[i];
            qq.push(kk);
        }
    }
}
void Pretreatment()
{
    node k;
    for(ll i=0; i<n; ++i)
        for(ll j=0; j<m; ++j)
            if(check(i,j))
            {
                tim[i][j]=1;
                k.X=i,k.Y=j,k.C=1;
                qq.push(k);
            }
    BFS();
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll x,y,k;
    cin>>n>>m>>t;
    for(ll i=0; i<n; ++i)
        cin>>mp[i];
    Pretreatment();
    while(t--)
    {
        cin>>x>>y>>k;
        x--,y--;
        ll ans=mp[x][y]-'0';
        if(tim[x][y]==0||k<tim[x][y]||k>=tim[x][y]&&(k-tim[x][y])&1)
            cout<<ans<<endl;
        else
            cout<<(1^ans)<<endl;
    }
    return 0;
}