题目链接

https://codeforces.com/problemset/problem/1360/E

题目描述

（来自于luogu）

解题思路

根据题目给出的样例可以得知，射出的第一颗子弹肯定会落在最底处或最右边，解题的关键就在于此，以最底处或最右边为基准，只能向上或向左填充阵地。

使用dfs从最底处或最右边向上或向左搜索，统计1的填充个数，和原始矩阵1的数量比较一下即可得出答案。

参考代码

#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 54;
bool mat[MAXN][MAXN];
bool flag[MAXN][MAXN];
int ans=0;void dfs(int x,int y){if( !mat[x][y] || flag[x][y] || x<=0 || y<=0) return ;if( mat[x][y] && !flag[x][y] )  {ans++;flag[x][y] = true;}//cout<<x<<" "<<y<<endl;dfs(x,y-1); //go topdfs(x-1,y); //go left
}
int main(){int t;char ch;cin>>t;	while( t-- ){int n;int num=0;ans=0;memset(mat,0,sizeof(mat));memset(flag,0,sizeof(flag));cin>>n;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++) {cin>>ch;mat[i][j] = ch - '0';if ( ch == '1' )num++;		}for(int i = 1; i <= n; i++){dfs( i, n);dfs( n, i);	}if( num == ans)  cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
} 

注：第一次提交时，dfs( )函数的第一行没有标记flag[x][y] ，很多区域重复访问，导致程序超时了。做题时还是需要细心细心再细心，指数级别的时间复杂度还是比较耗时的，不能存侥幸心理。