lightoj1012

maksyuki 发表于 oj 分类，标签: 基础算法-搜索(DFS\BFS)\记忆化

27 8月 2015

1012 - Guilty Prince

For simplicity, you can consider the place as a rectangular grid consisting of some cells. A cell can be a land or can contain water. Each time the prince can move to a new cell from his current position if they share a side.Once there was a king named Akbar. He had a son named Shahjahan. For an unforgivable reason the king wanted him to leave the kingdom. Since he loved his son he decided his son would be banished in a new place. The prince became sad, but he followed his father's will. In the way he found that the place was a combination of land and water. Since he didn't know how to swim, he was only able to move on the land. He didn't know how many places might be his destination. So, he asked your help.

Now write a program to find the number of cells (unit land) he could reach including the cell he was living.

Input

Input starts with an integer T (≤ 500), denoting the number of test cases.

Each case starts with a line containing two positive integers W and H; W and H are the numbers of cells in the x and y directions, respectively. W and H are not more than 20.

There will be H more lines in the data set, each of which includes W characters. Each character represents the status of a cell as follows.

1) '.' - land

2) '#' - water

3) '@' - initial position of prince (appears exactly once in a dataset)

Output

For each case, print the case number and the number of cells he can reach from the initial position (including it).

Sample Input

Output for Sample Input

46 9....#......#

......

#@...#

.#..#.

11 9

.#.........

.#.#######.

.#.#.....#.

.#.#.###.#.

.#.#..@#.#.

.#.#####.#.

.#.......#.

.#########.

...........

11 6

..#..#..#..

..#..#..###

..#..#..#@.

..#..#..#..

7 7

..#.#..

###.###

...@...

###.###

..#.#..

Case 1: 45Case 2: 59Case 3: 6Case 4: 13

题目类型：DFS/BFS

算法分析：调用DFS/BFS计算连通的’.’数量即可

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int maxn = 66 + 6;

const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};

char ans[maxn][maxn];
bool visited[maxn][maxn];

int sum, row, col, flag = 1, s_x, s_y;

inline bool OkMove (int x, int y)
{
    if (x >= 0 && x <= row - 1 && y >= 0 && y <= col - 1 && !visited[x][y] && ans[x][y] != '#')
        return true;

return false;
}


void DFS (int x, int y)
{
    int i;
    for (i = 0; i < 4; i++)
    {
        if (OkMove (x + dx[i], y + dy[i]))
        {
            int val_x = x + dx[i], val_y = y + dy[i];

            visited[val_x][val_y] = true;
            sum++;
            DFS (val_x, val_y);
        }
    }
}
int main()
{
//    ifstream cin ("aaa.txt");

    int t;
    cin >> t;

    while (t--)
    {
        cin >> col >> row;

        int i, j;
        for (i = 0; i < row; i++)
        {
            for (j = 0; j < col; j++)
            {
                cin >> ans[i][j];

                if (ans[i][j] == '@')
                {
                    s_x = i;
                    s_y = j;
                }
            }
        }

        memset (visited, false, sizeof (visited));
        sum = 1;

        visited[s_x][s_y] = true;

        DFS (s_x, s_y);

        cout << "Case " << flag++ << ": " << sum << endl;
    }

return 0;
}

#include <iostream>

#include <fstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int maxn = 66 + 6;

const int dx[] = {0, 0, -1, 1};

const int dy[] = {-1, 1, 0, 0};

char ans[maxn][maxn];

bool visited[maxn][maxn];

int sum, row, col, flag = 1, s_x, s_y;

inline bool OkMove (int x, int y)

{

if (x >= 0 && x <= row - 1 && y >= 0 && y <= col - 1 && !visited[x][y] && ans[x][y] != '#')

return true;

return false;

}

void DFS (int x, int y)

{

int i;

for (i = 0; i < 4; i++)

{

if (OkMove (x + dx[i], y + dy[i]))

{

int val_x = x + dx[i], val_y = y + dy[i];

visited[val_x][val_y] = true;

sum++;

DFS (val_x, val_y);

}

int main()

{

// ifstream cin ("aaa.txt");

int t;

cin >> t;

while (t--)

{

cin >> col >> row;

int i, j;

for (i = 0; i < row; i++)

{

for (j = 0; j < col; j++)

{

cin >> ans[i][j];

if (ans[i][j] == '@')

{

s_x = i;

s_y = j;

}

memset (visited, false, sizeof (visited));

sum = 1;

visited[s_x][s_y] = true;

DFS (s_x, s_y);

cout << "Case " << flag++ << ": " << sum << endl;

}

return 0;

}

lightoj1010

lightoj1014

一	二	三	四	五	六	日
« 6月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

超客的水墨烟雨

lightoj1012

Input

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论