Codeforces-1350 E.Orac and Game of Life

题目：

• 给出一个n * m 的矩阵，每个位置的值是0或1。可以对矩阵执行操作：将所有四周有和自己相同值的点反转(0->1,1->0)。有多组询问，输入x,y,p，输出(x,y)点在矩阵经过p次操作后的值。
• 首先一个四周存在相同值的点一次操作后值反转。一个四周没有和自己相同值的点，它在一次操作后值不变，但是这个点的四周的某个点可能会在在某次操作后改变。那么它到底在第几次操作后会改变呢？
• 一个点变了后会影响四周至少一个点变换，这个点变了后又继续影响其四周的点，所以一个初始时状态不变的点会受距离这个点最近(哈密顿距离)的点的影响。具体就是设dis[x][y]表示(x,y)距离最近的变化点的距离。ans = (p - dis[x][y]) % 2 ? a[x][y] ^ 1 : a[x][y], 注意：p<dis[x][y]时表示最近的点都影响不了(x,y)所以输出(x,y);

int n, m, T;
char s[N];
int a[N][N];
bool vis[N][N];
ll dis[N][N]; 
queue<PII> q;
int ax[5] = {0, 0, -1, 1};
int ay[5] = {1, -1, 0, 0};


void dfs(int x, int y){
    vis[x][y] = true;
    dis[x][y] = 0;
    q.push(PII(x,y));
    for(int i = 0; i <= 3; ++ i){
        int tx = x + ax[i], ty = y + ay[i];
        if(a[x][y] == a[tx][ty] && !vis[tx][ty]) 
            dfs(tx, ty);
    }
}


void bfs(){
    while(!q.empty()){
        PII p = q.front();
        q.pop();
        int x = p.first, y = p.second;
        for(int i = 0; i <= 3; ++ i){
            int tx = x + ax[i], ty = y + ay[i];
            if(a[tx][ty]!=-1 && dis[x][y] + 1 < dis[tx][ty]){
                dis[tx][ty] = dis[x][y] + 1;
                q.push(PII(tx, ty));
            }
        }
    }
}  

int main()
{
    memset(a,-1,sizeof(a));
    scanf("%d%d%d",&n,&m,&T);
    for(int i = 1; i <= n; ++ i){
        scanf("%s",s + 1);
        for(int j = 1; j <= m; ++ j){
            a[i][j] = s[j] - ‘0‘;
            dis[i][j] = INF;
        }
    }
    
   for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j)
            for(int k = 0; k <= 3; ++ k){
                int x = i + ax[k];
                int y = j + ay[k];
                if(a[x][y] == a[i][j]) {
                    dfs(i, j);
                    break;
                }
            }
            
     bfs();
     ll x, y, p;
     while(T --){
         scanf("%lld%lld%lld",&x,&y,&p);
         if(dis[x][y] >= p) printf("%d\n",a[x][y]);
         else printf("%d\n", (p - dis[x][y]) % 2 ? a[x][y] ^ 1 : a[x][y]);
     }
     return 0;
}

Codeforces-1350 E.Orac and Game of Life

原文：https://www.cnblogs.com/A-sc/p/12884190.html