拓扑排序：全RE求条QAQ

Question

麻烦哪位巨佬帮我看看，为什么改了成百上千次还是RE，一直RE
QAQ好无助……

题目 猫猫小游戏1（gameone）

题目描述

俨俨有一个 $n\times n$ 的网格，每个格子有一个颜色，初始都为无色。
俨俨喜欢花花绿绿的东西，因此它要对这个网格进行染色。它有两种染色方法：

• 任选一行，把该行的格子全部染成红色。
• 任选一列，把该列的格子全部染成绿色。
  俨俨可以无限次的采用上述方法进行染色，新的染色会覆盖以前的染色效果。
  $Smeow$ 对俨俨提出了多次询问，每次询问给出一张 $n\times n$ 的染过色的网格，保证每个格子都有颜色。俨俨需要回答，它能否采取上述染色方法，使得一个 $n\times n$ 的无色网格染成 $Smeow$ 给出的染色网格？

输入格式

第一行读入一个整数 $T$ ，表示询问的次数。
接下来会读入 $T$ 组数据：

• 每组数据的第一行是一个整数 $n$ ，表示网格是$n\times n$的。
• 接下来 $n$ 行，每行一个字符串，第 $i$ 行第 $j$ 个字符表示第 $i$ 行第 $j$ 列网格的颜色，为 $0$ 表示红色，为 $1$ 表示绿色，没有其他字符。

  输出格式

  对于每组数据输出一行一个字符串，若俨俨能够成功染色出该网格，则输出Yes，否则输出No。

样例 #1

样例输入 #1

3
1
1
2
10
01
2
11
01

样例输出 #1

Yes
No
Yes

样例 #2

样例输入 #2

3
3
111
000
111
3
101
111
000
3
100
000
001

样例输出 #2

Yes
Yes
No

数据范围与约定

对于 $50%$ 的数据， $T\le10,n\le9$

对于 $70%$ 的数据， $T\le10,n\le50$

对于 $100%$ 的数据， $T\le10,n\le1000$

我的代码：

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;


const int N=1013;
int head[2*N],indeg[2*N];
int tot=0,T,n;

struct edge{
    int to;
    int nxt;
}e[N*N*4];

void add(int u,int v){
    e[++tot].to=v;
    e[tot].nxt=head[u];
    head[u]=tot;
}

bool judge(int n,vector<string>& grid){
    tot=0;
    for (int i=1;i<=2*n;i++){
        head[i]=indeg[i]=0;
    }
    
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++){
            if (grid[i-1][j-1]=='0'){
                add(i,n+j);
                indeg[n+j]++;
            }
            else {
                add(n+j,i);
                indeg[i]++;
            }
        }
    queue <int> q;
    int cnt=0;
    for (int i=1;i<=n*2;i++){
        if (indeg[i]==0) q.push(i);
    }
    while (!q.empty()){
        int u=q.front();
        q.pop();
        cnt++;
        for (int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            indeg[v]--;
            if (indeg[v]==0) q.push(v);
        }
    }
    
    return cnt==2*n;
}



int main(){
    
//    freopen("gameone_ex.in","r",stdin);
//  freopen("gameone_ex.out","w",stdout);
    
    cin>>T;
    while(T--){
        cin>>n;
        vector <string> grid(n);
        for (int i=0;i<n;i++)
            cin>>grid[i];
        if (judge(n,grid)) cout<<"Yes\n";
        else cout<<"No\n";
    }
    
    return 0;
    
}

Answer 1

让 “紫雾凌寒” 来帮你回答,本回答结合 DeepSeek

如果还有问题，请评论或点击头像私信，如果有帮助到您, 请关注、采纳、点赞

1. 关键点分析：
   - 仅给出了题目描述，没有看到具体代码。RE（运行时错误）通常是由于多种原因导致的，比如数组越界访问、空指针引用、除零错误等。
   - 对于这个题目，由于没有代码，很难确切知道问题所在。但可能在对n×n网格进行操作时，存在访问超出网格范围的情况，或者在处理颜色相关操作时出现了非法访问。
2. 解决方案示例：
   - 假设这里是用C++ 处理网格相关操作，比如初始化网格：

#include <iostream>
const int MAX_N = 100;
int grid[MAX_N][MAX_N];

void initGrid(int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            grid[i][j] = 0; // 初始颜色设为无，这里假设用0表示
        }
    }
}

• 如果在后续操作中出现RE，比如访问grid[i][j]时，要确保0 <= i < n且0 <= j < n。例如，遍历网格的代码：

void printGrid(int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cout << grid[i][j] << " ";
        }
        std::cout << std::endl;
    }
}

• 这里要注意不能出现i >= n或者j >= n的情况，否则就会导致数组越界访问，从而引发RE。
  3. 多种解决方案及优缺点：
• 增加边界检查：
  • 优点：可以直接避免数组越界访问这种常见的RE原因。在每次访问数组元素前进行边界判断，逻辑清晰。
  • 缺点：会增加代码量，特别是在多层嵌套循环访问数组时，每个访问点都要增加边界检查代码，可能会影响代码的简洁性。
• 使用更安全的数据结构：
  • 优点：比如使用std::vector代替普通数组，std::vector会自动管理内存，并且在访问时会进行边界检查，相对更安全。
  • 缺点：会增加一些额外的开销，比如内存管理的开销。并且如果对性能要求较高，频繁的边界检查可能会有一定影响。
    4. 总结：
• 出现RE通常是由于程序运行时发生了非法操作。对于网格相关问题，很可能是数组越界访问。通过增加边界检查或者使用更安全的数据结构可以解决这类问题。在没有看到具体代码的情况下，只能推测可能的原因并提供通用的解决思路。需要结合具体代码进一步排查问题。

希望以上解答对您有所帮助。如果您有任何疑问，欢迎在评论区提出。