本文共 1696 字，大约阅读时间需要 5 分钟。

首先不难发现发出的1肯定是先出现边界，然后1出现在和边界相连的1，一次向上或向左连接成连通块，那么我们考虑第一种做法：从所有的边界存在1的地方搜索，然后对连通块上的1进行标记。最后对整个$n\times m$的方阵中所有的1如果存在不被标记的就是NO，否则为YES

还有一种简单的方法：只需看除了边界的每一个1的右边或者下边是否有1，如果都合法则正确，否则错误

第一种方法：

#include <set>#include <map>#include <stack>#include <queue>#include <math.h>#include <cstdio>#include <string>#include <cstring>#include <sstream>#include <iostream>#include <algorithm>#include <unordered_map>using namespace std;#define lowbit(x) (x&(-x))typedef long long ll;typedef unsigned long long ull;typedef pair<int,int> P;const double eps=1e-8;const double pi=acos(-1.0);const int inf=0x3f3f3f3f;const ll INF=1e18;const int Mod=1e9+7;const int maxn=2e5+10;int n;int a[105][105];bool vis[105][105];const int dx[]={   0,-1};const int dy[]={   -1,0};void dfs(int r,int c){       vis[r][c]=1;    if(a[r][c]==0) return;    for(int i=0;i<2;i++){           int x=r+dx[i],y=c+dy[i];        if(!vis[x][y] && r>=1 && r<=n && y>=1 && y<=n)            dfs(x,y);    }}int main(){       //freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout);    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);    int t;    char c;    cin>>t;    while(t--){           cin>>n;        memset(vis,0,sizeof vis);        for(int i=1;i<=n;i++)            for(int j=1;j<=n;j++){                   cin>>c;                a[i][j]=c-'0';            }        for(int i=1;i<=n;i++)            if(!vis[n][i] && a[i][n]) dfs(i,n);        for(int i=1;i<=n;i++)            if(!vis[n][i] && a[n][i]) dfs(n,i);        int flag=0;        for(int i=1;i<=n;i++)            for(int j=1;j<=n;j++){                   if(!vis[i][j] && a[i][j]) flag=1;            }        if(flag) cout<<"NO\n";        else cout<<"YES\n";    }    return 0;}

转载地址：http://iuqq.baihongyu.com/