Friday, 19 February 2016

Light OJ 1012 (Guilty Prince)

#include<bits/stdc++.h>
using namespace std;
int x[4]={-1,0,1,0};
int y[4]={0,-1,0,1};
int graph[100][100];
int visited[100][100];
int level[100][100];
int main()
{
    int test,k;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        for(int i=0;i<100;i++)
        {
            for(int j=0;j<100;j++)
            {
                graph[i][j]=0;
                visited[i][j]=0;
                level[i][j]=0;
            }
        }
        int r,c,stx,sty;
        cin>>r>>c;
        for(int i=0;i<c;i++)
        {
            string s;
            cin>>s;
            for(int j=0;j<r;j++)
            {
                if(s[j]=='.')
                    graph[i][j]=0;
                if(s[j]=='#')
                    graph[i][j]=1;
                if(s[j]=='@')
                {
                    stx=i;
                    sty=j;
                    graph[i][j]=0;
                }
            }

        }
        queue<int>q;
        q.push(stx);
        q.push(sty);
        visited[stx][sty]=1;
        level[stx][sty]=0;
        int cnt=0;
        while(!q.empty())
        {
            int f1=q.front();
            q.pop();
            int f2=q.front();
            q.pop();
            for(int i=0;i<4;i++)
            {
                int v1=f1+x[i];
                int v2=f2+y[i];
                if(visited[v1][v2]!=1&&graph[v1][v2]==0&&v1>=0&&v1<c&&v2>=0&&v2<r)
                {
                    cnt++;
                    //cout<<cnt<<endl;
                    visited[v1][v2]=1;
                    q.push(v1);
                    q.push(v2);
                }
            }
        }
        cout<<"Case "<<k<<": "<<cnt+1<<endl;
    }
    return 0;
}

No comments:

Post a Comment