OpenJudge 2815 城堡问题 / Poj 1164 The Castle

时间:2022-10-15 21:12:37

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是一个城堡的地形图。请你编写一个程序,计算城堡一共有多少房间,最大的房间有多大。城堡被分割成mn(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的更多相关文章

  1. &lbrack;POJ&rsqb;1164 The Castle

    //markdown复制进来一堆问题 还是链接方便点 POJ 1164 The Castle 首先想到用9个方格来表示一个房间,如此一来复杂许多,MLE代码如下: //Writer:GhostCai ...

  2. 百练oj 2815&colon;城堡问题(dfs)

    传送门: http://bailian.openjudge.cn/practice/2815 2815:城堡问题 查看 提交 统计 提示 提问 总时间限制: 1000ms 内存限制: 65536kB ...

  3. POJ 1164 城堡问题【DFS&sol;位运算&sol;种子填充法&sol;染色法】

    1 2 3 4 5 6 7 ############################# 1 # | # | # | | # #####---#####---#---#####---# 2 # # | ...

  4. POJ 1164:The Castle

    The Castle Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 6677   Accepted: 3767 Descri ...

  5. 【OpenJudge 191】【POJ 1189】钉子和小球

    http://noi.openjudge.cn/ch0405/191/ http://poj.org/problem?id=1189 一开始忘了\(2^{50}\)没超long long差点写高精度Q ...

  6. OpenJudge 2803 碎纸机 &sol; Poj 1416 Shredding Company

    1.链接地址: http://poj.org/problem?id=1416 http://bailian.openjudge.cn/practice/2803 2.题目: 总时间限制: 1000ms ...

  7. OpenJudge 2802 小游戏 &sol; Poj 1101 The Game

    1.链接地址: http://bailian.openjudge.cn/practice/2802 http://poj.org/problem?id=1101 2.题目: 总时间限制: 1000ms ...

  8. OpenJudge 2813 画家问题 &sol; Poj 1681 Painter&&num;39&semi;s Problem

    1.链接地址: http://bailian.openjudge.cn/practice/2813 http://poj.org/problem?id=1681 2.题目: 总时间限制: 1000ms ...

  9. OpenJudge 2811 熄灯问题 &sol; Poj 1222 EXTENDED LIGHTS OUT

    1.链接地址: http://bailian.openjudge.cn/practice/2811 http://poj.org/problem?id=1222 2.题目: 总时间限制: 1000ms ...

随机推荐

  1. asp&period;net 捕获throw

    <script type="text/javascript"> function pageLoad() { Sys.WebForms.PageRequestManage ...

  2. DDD:整理了一些关于验证方面的文章

    http://msdn.microsoft.com/en-us/library/ff664356(v=pandp.50).aspx http://gorodinski.com/blog/2012/05 ...

  3. Ajax学习资源大全&lbrack;本来是转载的&comma;但是现在我增加了很多&rsqb;

    本欲放转载区,但是这样一文章放那里基本是没有用的,帮助不了任何人!所以放新手了!! 我一般非经典或者自己用不上不转载,所以如果你不幸看见了的话,恰恰你又对AJAX有兴趣的话不防看下,也许对你有用的!! ...

  4. Sql Server 维护计划 备份覆盖

            之前在设置服务器Sql Server 维护计划 备份的sql server 数据库,都是累加的,后来也没有仔细看过,后台回过头来考虑到服务器的存储空间,只好做sql server 数据 ...

  5. C与C&plus;&plus;动态分配二维数组

    C: C中使用函数malloc和free两个函数. //动态分配M*N维 int **a=(int **)malloc(sizeof(int*)*M); ;i<M;i++) a[i]=(int ...

  6. de4dot命令 v2&period;0&period;3&period;3405

    de4dot v2.0.3.3405 Copyright (C) 2011-2013 [email]de4dot@gmail.com[/email] Latest version and source ...

  7. nginx二级域名配置自动跳转到一级域名

    nginx二级域名配置自动跳转到一级域名 rewrite配置内容: if ($http_host !~ "^www.aaa.com$") { rewrite ^(.*) http: ...

  8. &lbrack;Swift&rsqb;LeetCode731&period; 我的日程安排表 II &vert; My Calendar II

    Implement a MyCalendarTwoclass to store your events. A new event can be added if adding the event wi ...

  9. angular路由为空重定向到指定路由

    { path: '', redirectTo: 'home', pathMatch: 'full' }

  10. 「SHOI2015」(LOJ2038)超能粒子炮・改

    传送门:Here 一句话题意:给定$ t$次询问,每次读入$n,k,$求$ \sum_{i=0}^kC_n^k\ mod\ 2333$, 其中$ t \leq 100000$,$n,k \leq 10 ...