1.链接地址:
http://bailian.openjudge.cn/practice/2815/
http://poj.org/problem?id=1164
2.题目:
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
1 2 3 4 5 6 7
#############################
1 # | # | # | | #
#####---#####---#---#####---#
2 # # | # # # # #
#---#####---#####---#####---#
3 # | | # # # # #
#---#########---#####---#---#
4 # # | | | | # #
#############################
(图 1) # = Wall
| = No wall
- = No wall图1是一个城堡的地形图。请你编写一个程序,计算城堡一共有多少房间,最大的房间有多大。城堡被分割成mn(m≤50,n≤50)个方块,每个方块可以有0~4面墙。
- 输入
- 程序从标准输入设备读入数据。第一行是两个整数,分别是南北向、东西向的方块数。在接下来的输入行里,每个方块用一个数字(0≤p≤50)描
述。用一个数字表示方块周围的墙,1表示西墙,2表示北墙,4表示东墙,8表示南墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次,方块
(1,1)的南墙同时也是方块(2,1)的北墙。输入的数据保证城堡至少有两个房间。- 输出
- 城堡的房间数、城堡中最大房间所包括的方块数。结果显示在标准输出设备上。
- 样例输入
4
7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13- 样例输出
5
9- 来源
- 1164
3.思路:
深搜
4.代码:
#include <iostream>
#include <cstdio> using namespace std; int idx_x[] = {-,,,};
int idx_y[] = {,-,,}; int m,n; int f(int **arr,int i,int j)
{
//cout << "f(" << i << "," << j << ")" << endl; /*for(int y = 0; y < m; ++y)
{
for(int x = 0; x < n; ++x)
{
cout << arr[y][x] << " ";
}
cout << endl;
}*/ if(i < || i >= m || j < || j >= n || arr[i][j] == -) return ;
int value = arr[i][j]; int res = ;
int k;
arr[i][j] = -;
for(k = ; k < ; ++k)
{
if(value % == ) res += f(arr,i + idx_y[k],j + idx_x[k]);
value /= ;
}
return res;
} int main()
{
//freopen("C://input.txt","r",stdin); int i,j; //int m,n;
cin >> m >> n; int **arr = new int*[m];
for(i = ; i < m; ++i) arr[i] = new int[n]; for(i = ; i < m; ++i)
{
for(j = ; j < n; ++j)
{
cin >> arr[i][j];
}
} int count = ;
int max = ;
int num;
for(i = ; i < m; ++i)
{
for(j = ; j < n; ++j)
{
if(arr[i][j] != -)
{
num = f(arr,i,j);
//cout << "num=" << num << endl;
if(max < num) max = num;
++count;
}
}
}
cout << count << endl;
cout << max << endl; for(i = ; i < m; ++i) delete [] arr[i];
delete [] arr; return ;
}
OpenJudge 2815 城堡问题 / Poj 1164 The Castle的更多相关文章
-
[POJ]1164 The Castle
//markdown复制进来一堆问题 还是链接方便点 POJ 1164 The Castle 首先想到用9个方格来表示一个房间,如此一来复杂许多,MLE代码如下: //Writer:GhostCai ...
-
百练oj 2815:城堡问题(dfs)
传送门: http://bailian.openjudge.cn/practice/2815 2815:城堡问题 查看 提交 统计 提示 提问 总时间限制: 1000ms 内存限制: 65536kB ...
-
POJ 1164 城堡问题【DFS/位运算/种子填充法/染色法】
1 2 3 4 5 6 7 ############################# 1 # | # | # | | # #####---#####---#---#####---# 2 # # | ...
-
POJ 1164:The Castle
The Castle Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 6677 Accepted: 3767 Descri ...
-
【OpenJudge 191】【POJ 1189】钉子和小球
http://noi.openjudge.cn/ch0405/191/ http://poj.org/problem?id=1189 一开始忘了\(2^{50}\)没超long long差点写高精度Q ...
-
OpenJudge 2803 碎纸机 / Poj 1416 Shredding Company
1.链接地址: http://poj.org/problem?id=1416 http://bailian.openjudge.cn/practice/2803 2.题目: 总时间限制: 1000ms ...
-
OpenJudge 2802 小游戏 / Poj 1101 The Game
1.链接地址: http://bailian.openjudge.cn/practice/2802 http://poj.org/problem?id=1101 2.题目: 总时间限制: 1000ms ...
-
OpenJudge 2813 画家问题 / Poj 1681 Painter&#39;s Problem
1.链接地址: http://bailian.openjudge.cn/practice/2813 http://poj.org/problem?id=1681 2.题目: 总时间限制: 1000ms ...
-
OpenJudge 2811 熄灯问题 / Poj 1222 EXTENDED LIGHTS OUT
1.链接地址: http://bailian.openjudge.cn/practice/2811 http://poj.org/problem?id=1222 2.题目: 总时间限制: 1000ms ...
随机推荐
-
asp.net 捕获throw
<script type="text/javascript"> function pageLoad() { Sys.WebForms.PageRequestManage ...
-
DDD:整理了一些关于验证方面的文章
http://msdn.microsoft.com/en-us/library/ff664356(v=pandp.50).aspx http://gorodinski.com/blog/2012/05 ...
-
Ajax学习资源大全[本来是转载的,但是现在我增加了很多]
本欲放转载区,但是这样一文章放那里基本是没有用的,帮助不了任何人!所以放新手了!! 我一般非经典或者自己用不上不转载,所以如果你不幸看见了的话,恰恰你又对AJAX有兴趣的话不防看下,也许对你有用的!! ...
-
Sql Server 维护计划 备份覆盖
之前在设置服务器Sql Server 维护计划 备份的sql server 数据库,都是累加的,后来也没有仔细看过,后台回过头来考虑到服务器的存储空间,只好做sql server 数据 ...
-
C与C++动态分配二维数组
C: C中使用函数malloc和free两个函数. //动态分配M*N维 int **a=(int **)malloc(sizeof(int*)*M); ;i<M;i++) a[i]=(int ...
-
de4dot命令 v2.0.3.3405
de4dot v2.0.3.3405 Copyright (C) 2011-2013 [email]de4dot@gmail.com[/email] Latest version and source ...
-
nginx二级域名配置自动跳转到一级域名
nginx二级域名配置自动跳转到一级域名 rewrite配置内容: if ($http_host !~ "^www.aaa.com$") { rewrite ^(.*) http: ...
-
[Swift]LeetCode731. 我的日程安排表 II | My Calendar II
Implement a MyCalendarTwoclass to store your events. A new event can be added if adding the event wi ...
-
angular路由为空重定向到指定路由
{ path: '', redirectTo: 'home', pathMatch: 'full' }
-
「SHOI2015」(LOJ2038)超能粒子炮・改
传送门:Here 一句话题意:给定$ t$次询问,每次读入$n,k,$求$ \sum_{i=0}^kC_n^k\ mod\ 2333$, 其中$ t \leq 100000$,$n,k \leq 10 ...