题目标签

CF1360E

难度

普及/提高-

思路分析

思路一

时间复杂度 $O(n^2t)$

说实在，这一题其实很简单。一道纯模拟题。我们先来分析一下题目：“且遇到边界后会停止，遇到一个停止的子弹也会停止”。这个点可以说明每一个子弹的最终坐标只可能在边界上，或者右方/下方有一个子弹。如果这些条件都不满足，这种答案是错误的。因为我们来想想，炮弹往右射出去，必定要碰到边界和子弹才会停下来。可出现了还没碰到边际和子弹就停下来的情况是不可能的。所以只需判断是否存在上述情况即可。当有出现这种情况时，则停止循环，输出 $N O$ 。否则，输出 $Y E S$ 。

从代码来分析，首先要求输入一个边长为 $n$ 的正方形矩阵，那每次循环只需要把这个矩阵的所有数组循环一次就好了。先来分析一下在边界的情况。如何判断是否在边界呢？其实很简单。只要把矩阵的右面一层和下面一层全部用 $1$ 扫过一边就OK了。

	//这些是用1扫过的for(int i=1;i<=n;i++)a[i][n+1]=1;for(int i=1;i<=n;i++)a[n+1][i]=1;

把在矩阵范围内的 $1$ 判断完毕就好了。出现这种情况的时候是右面和下面都为 $0$ 的时候。这样就简单了。

	bool g=true;//这个bool是用来判断是否有出现 NO 的情况for(int i=1;i<=n&&g;i++)for(int j=1;j<=n&&g;j++)if(a[i][j]==1&&!(a[i+1][j]==1||a[i][j+1]==1)){cout<<"NO"<<endl;g=false;}if(g)cout<<"YES"<<endl;

错因分析

1.把 $0$ 都当做 $1$ 来扫了，这样是错的！！！只有当前有子弹时才扫，没子弹时扫了没有意义。~~（似乎也就这一个错因）~~

AC代码

#include<iostream>
using namespace std;
int main()
{
int t;
cin>>t;
for(int h=1;h<=t;h++){bool g=true;string b;int a[55][55]={0},n;cin>>n;for(int i=1;i<=n;i++){cin>>b;for(int j=1;j<=n;j++)a[i][j]=b[j-1]-48;}for(int i=1;i<=n;i++)a[i][n+1]=1;for(int i=1;i<=n;i++)a[n+1][i]=1;for(int i=1;i<=n&&g;i++)for(int j=1;j<=n&&g;j++)if(a[i][j]==1&&!(a[i+1][j]==1||a[i][j+1]==1)){cout<<"NO"<<endl;g=false;}if(g)cout<<"YES"<<endl;
}	
return 0;
}