Orac and Game of Life CodeForces

#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define int long long
const int N=1010;
typedef pair<int,int>pii;
int n,m,Q;
char s[N];
int a[N][N];
int f[N][N];
int tx[]={1,0,-1,0};
int ty[]={0,1,0,-1};
signed main()
{
	cin>>n>>m>>Q;
	for(int i=1;i<=n;i++)
	{
		cin>>s+1;
		for(int j=1;j<=m;j++)
			a[i][j]=(s[j]=='1' );
	}
	queue<pii>q;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int k=0;k<4;k++)
			{
				int xx=i+tx[k],yy=j+ty[k];
				if(xx>0&&xx<=n&&yy>0&&yy<=m&&a[i][j]==a[xx][yy])
					f[i][j]=f[xx][yy]=1;
			}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(f[i][j])
				q.push({i,j});
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		int x=t.first,y=t.second;
		for(int i=0;i<4;i++)
		{
			int xx=x+tx[i],yy=y+ty[i];
			if(xx>0&&xx<=n&&yy>0&&yy<=m&&!f[xx][yy])
			{
				f[xx][yy]=f[x][y]+1;
				q.push({xx,yy});
			}
		}
	}
	while(Q--)
	{
		int x,y,k;
		cin>>x>>y>>k;
		if(!f[x][y] || f[x][y]>k)
			cout<<a[x][y]<<endl;
		else
		{
			if((k-f[x][y]+1)&1)
				cout<<!a[x][y]<<endl;
			else
				cout<<a[x][y]<<endl;
		} 
	}
}