CVBB ACM Team

题目链接

题目大意：

给定一个只含0，1的二维矩阵，判断这个矩阵是否合法。

题目背景是发射炮弹，一个炮弹的前方是尽头或者是其他的炮弹时，会停下。

解决方法是对每个炮弹（1）进行dfs，如果他的右侧或下册同时出现（0），则这个炮弹是非法的，有一个炮弹是非法的，则这个矩阵就是非法

的，反之就是合法的矩阵。

AC代码：

#include<cstdio>
#include<algorithm>
#include<iostream>
#define bug printf("!!!!!\n")
const int MAX_N=105;
char s[110], laji[110];
int N,M,sx,sy,flag;
int field[MAX_N][MAX_N+1];
bool dfs(int x, int y){
	if(x == N - 1 || y == M - 1) {
		return true; 
	}
		int nx=x,ny=y+1;
		int nx1=x+1,ny1=y;
		if(field[nx][ny]==0&&field[nx1][ny1]==0){
				return false;
 
			} 
	return true;
}
void solve(){
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			if(field[i][j] == 1)	{
				if (! dfs(i,j)) {
					printf("NO\n");
					return;
				}
			}	
			}
		}
	printf("YES\n");
	return;
}
int main()
{
	int t;
	scanf("%d", &t);
	while(t--)
	{	
		scanf("%d",&N);
		gets(laji);
		M = N;
		flag=1;
		for(int i=0;i<N;i++){
			gets(s);
			for(int j=0;j<M;j++){
				field[i][j]=s[j]-'0';
				}
		}
		solve();
	}
return 0;
}