LightOJ 1337-The Crystal Maze

You are in a plane and you are about to be dropped with a parasuit in a crystal maze. As the name suggests, the maze is full of crystals. Your task is to collect as many crystals as possible.

To be more exact, the maze can be modeled as an M x N 2D grid where M denotes the number of rows and N denotes the number of columns. There are three types of cells in the grid:

1. A '#' denotes a wall, you may not pass through it.
2. A 'C' denotes a crystal. You may move through the cell.
3.  A '.' denotes an empty cell. You may move through the cell.

     Now you are given the map of the maze, you want to find where to land such that you can collect maximum number of crystals. So, you are spotting some position x, y and you want to find the maximum number of crystals you may get if you land to cell (x, y). And you can only move vertically or horizontally, but you cannot pass through walls, or you cannot get outside the maze.

 

Input

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

Each case starts with a line containing three integers M, N and Q (2 ≤ M, N ≤ 500, 1 ≤ Q ≤ 1000). Each of the next M lines contains N characters denoting the maze. You can assume that the maze follows the above restrictions.

Each of the next Q lines contains two integers x_i and y_i (1 ≤ x_i ≤ M, 1 ≤ y_i ≤ N) denoting the cell where you want to land. You can assume that cell (x_i, y_i) is empty i.e. the cell contains '.'.

 

Output

For each case, print the case number in a single line. Then print Q lines, where each line should contain the maximum number of crystals you may collect if you land on cell (x_i, y_i).

Sample Input	Output for Sample Input
1 4 5 2 ..#.. .C#C. ##..# ..C#C 1 1 4 1	Case 1: 1 2

Analysis

We have to collect maximum number of crystal maze. By using DFS algorithm, we can count the number of crystal maze. From DFS algorithm we have known how to traverse reachable nodes from any node.

Solution

#include<bits/stdc++.h>
using namespace std;
int xx[]= {1,-1,0,0};
int yy[]= {0,0,1,-1};
char s[505][505];
int visit[505][505];
int r, c, p, qo;
int ans[1005];

int dfs(int ux, int uy)
{
    if(s[ux][uy]=='C')
    {
        qo++;
    }
    for(int i=0; i<4; i++)
    {
        int vx=ux+xx[i];
        int vy=uy+yy[i];

        if(vx<0 || vy<0 || vx>=r || vy>=c)
            continue;

        if(visit[vx][vy]!=0 || s[vx][vy]=='#')
            continue;

        visit[vx][vy]=p;
        dfs(vx,vy);
    }
}

int main()
{
    int t_case, t=0, a, b, q;
    scanf("%d", &t_case);
    while(t_case--)
    {
        memset(visit, 0, sizeof(visit));
        memset(ans, 0, sizeof(ans));
        p=1;
        scanf("%d%d%d", &r, &c, &q);
        for(int i=0; i<r; i++)
        {
            scanf("%s", s[i]);
        }
        printf("Case %d:\n", ++t);
        for(int j=0; j<q; j++)
        {
            scanf("%d%d", &a, &b);
            a=a-1;
            b=b-1;
            if(visit[a][b]==0)
            {
                qo=0;
                visit[a][b]=p;
                dfs(a, b);
                ans[p]=qo;
                p++;
            }
            printf("%d\n", ans[visit[a][b]]);
        }
    }
    return 0;
}