/* 这道题本来用广度递归来实现,编写完后发现AC不了,想想应该是 爆栈了,后来有改成用广度队列来写,可以AC啦! 思路是: 考虑到圈外的点肯定会和边框相交,所以就先把四条边的非0点入队, 入队一个点,就把这个点变成0, 然后在队列里面做第一个元素,找他的上下左右四个相邻非0点入队, 然后在队列里面做第二个元素,找他的上下左右四个相邻非0点入队, .............. 一直到top==base */ #include<stdio.h> #include<string.h> int map[965][1445];//存图 int queue[960*1440];//队列 int fang[4][2]={-1,0,1,0,0,-1,0,1};//方向数组 int W,H,base,top; int main() { // freopen("in.txt","r",stdin); int T; int i,j; scanf("%d",&T); while(T--) { base=0;top=0; memset(map,0,sizeof(map));//初始化 scanf("%d%d",&W,&H); for(i=1;i<=H;i++) for(j=1;j<=W;j++) scanf("%d",&map[i][j]);//存图 for(i=1;i<=H;i++)//第一行与最后一行入队 { if(map[i][1])queue[top++]=i*10000+1,map[i][1]=0;//用整形数存放坐标(节约空间,人人有责!) if(map[i][W])queue[top++]=i*10000+W,map[i][W]=0;//别忘了标记访问过的map为0哦! } for(j=1;j<=W;j++)//第一列与最后一列入队 { if(map[1][j])queue[top++]=1*10000+j,map[1][j]=0; if(map[H][j])queue[top++]=H*10000+j,map[H][j]=0; } while(top!=base)//一直到队列为空 { int x1,y1; for(i=0;i<4;i++) { x1=queue[base]/10000+fang[i][0]; y1=queue[base]%10000+fang[i][1];//求出这个点四周的坐标 if(map[x1][y1]) { queue[top++]=x1*10000+y1;//入队 map[x1][y1]=0;//标记 } } base++;//别忘记了哦! } for(i=1;i<=H;i++)//按格式输出 { for(j=1;j<W;j++)printf("%d ",map[i][j]); printf("%d\n",map[i][W]); } } return(0); }
相关推荐
南阳理工oj离线题库
南阳理工学院OJ第1版解题报告V1.0.pdf
南阳理工学院OJ_个人AC代码包(Java提交) 是Java初学者登堂入室的很好例子。
南阳理工学院stl练习场全部ac代码!
南阳理工ACM离线题库
哈理工OJ1084答案哈理工OJ1084答案哈理工OJ1084答案哈理工OJ1084答案哈理工OJ1084答案
西安理工大学学生在线实验系统编程题答案(超级详细)
基于Laravel 5.0的OJ题解网站 , 目前涵盖安科OJ,南阳OJ,杭电OJ ,北大OJ,浙大OJ.zip
山东理工大学2016级OJ进程,始于悦行,终于诚信。
(1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj...
趣味题:柱状图排序 西安理工大学学生在线实验系统 oj
DFS:depth first search深度优先搜索(迷宫寻路) BFS:breadth first search宽度优先搜索(迷宫最短路径) OJ习题答案
已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历,但已知先序和后序,却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及先序遍历结果,要求输出其后序遍历结果...
湖南理工学院OJ的0-100题解.rar
在线OJ网址大全在线OJ网址大全在线OJ网址大全在线OJ网址大全
山东理工大学2016级OJ题目1833
山东理工大学2016级OJ题目1834
搭建OJ平台的工具,方便大家搭建自己的OJ,建议大家使用ubuntu14.04版本,比较稳定
厦门理工学院软件工程重点课件,考试前抱佛脚可用。
OJ习题.zip