24h購物| | PChome| 登入
2013-01-21 07:03:26| 人氣1,065| 回應0 | 上一篇 | 下一篇

[ZJ][DFS/BFS] a597. 祖靈被榨乾了!!!!!!!!

推薦 0 收藏 0 轉貼0 訂閱站台

內容 :

段考結束了!!!!!!!

祖靈藉著他的外掛技能 "祖靈的祝福" 在段考上電爆全場,勇奪全校第一!!!!

祖靈他對此感到非常的高興.....

於是他回去他的房間延續他的好心情!!

於是祖靈在房間拼命的JIZZ,抱著超好的心情:)

但是繼之前祖靈已經榨出太多碗JIZZ麵了,他的身體已經不堪負荷了!!!!!

於是祖靈倒下了.........

-------------------警察來到了案發現場--------------------

A警:「這個人太猛了吧!!!整個房間快要遍全白了!!!!」

B警默默點頭表示認同......

A警:「他的身體也太猛了吧!!一定要請科學家來看看!!!」

於是科學家來了!!但是由於祖靈他房間實在太大而且有太多JIZZ了!!!! 無法當場調查....

於是請你幫幫科學家

給你他房間平面圖的長與寬,和平面圖,

幫他計算祖靈他房間有幾攤JIZZ,和最大那攤JIZZ的面積是多少。

 一攤JIZZ就是每一個J都在互相的上下左右,例:

XXJX

XJJJ

XXJX 

 J

JJJ

 J

即為一攤JIZZ。

然而

XJ

JX

則是兩攤JIZZ。 

輸入說明 :

總共有500筆測資。

每筆測資開頭為 m,n ,分別代表祖靈房間平面圖的長與寬。 ( 0<m, n<=500 , m行長度為n,對不起忘記說:P )

再來是一個圖  ( 請見範例輸入 ) 

其中 'X' 代表那個單位沒有祖靈的JIZZ , 'J'代表那個單位有祖靈的JIZZ。 

輸出說明 :

輸出總共有幾攤祖靈的JIZZ,和最大的那攤JIZZ覆蓋了多少單位。 

範例輸入 :

5 5
XXXXX
XXJJX
XJJJX
XXXXX
XJXXX

範例輸出 :

2 5

提示 :

背景知識: BFS

出處 :

成為祖靈的祖靈 (管理:eop112358130)

找連通元件,懶得使用 QUEUE,直接使用內有的 STACK


/**********************************************************************************/
/*  Problem: a597 "祖靈被榨乾了!!!!!!!!" from 成為祖靈的祖靈         */
/*  Language: C (868 Bytes)                                                       */
/*  Result: AC(820ms, 812KB) judge by this@ZeroJudge                              */
/*  Author: morris1028 at 2013-01-20 10:17:09                                     */
/**********************************************************************************/


#include <stdio.h>
#include <string.h>
char g[505][505], used[505][505];
int n, m, tmp;
void dfs(int x, int y) {
    if(x < 0 || y < 0 || x >= m || y >= n)
        return ;
    if(used[x][y] == 1 || g[x][y] != 'J')
        return ;
    used[x][y] = 1, tmp++;
    dfs(x+1, y), dfs(x-1, y);
    dfs(x, y+1), dfs(x, y-1);
}
int main() {
    int i, j;
    while(scanf("%d %d", &m, &n) == 2) {
        while(getchar() != '\n');
        for(i = 0; i < m; i++)
            gets(g[i]);
        memset(used, 0, sizeof(used));
        int cnt = 0, mx = 0;
        for(i = 0; i < m; i++)
            for(j = 0; j < n; j++)
                if(g[i][j] == 'J' && used[i][j] == 0) {
                    cnt++, tmp = 0, dfs(i, j);
                    mx = mx > tmp ? mx : tmp;
                }
        printf("%d %d\n", cnt, mx);
    }
    return 0;
}

台長: Morris
人氣(1,065) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][BIT+DP] a596. 祖靈要段考了!!!!!!!!
此分類上一篇:[ZJ][0/1背包] a587. 祖靈好孝順 ˋˇˊ

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文