Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

1111

Posted by SDRJ10484 at 2012-05-08 14:49:42
#include <stdio.h>
#include <queue>
using namespace std;

const int dsx1[4] = {1,0,-1,0};
const int dsy1[4] = {0,1,0,-1};
const int dsx2[4] = {1,-1,-1,1};
const int dsy2[4] = {1,1,-1,-1};

int width;
int height;
int startX,startY;
char Maps[25][25];
bool visited[25][25];

const bool bound(int _x,int _y)
{
    return (_x >=0 && _x < width)&&(_y >= 0 && _y < height);
}

int BFS()
{
    int ret = 0;
    if (Maps[startY][startX] !='X')
    {
        return 0;
    }
    memset(visited,0,sizeof(visited));
    queue<int> que;
    que.push(startY*100 + startX);
    visited[startY][startX] = true;
    while(!que.empty())
    {
        int curId = que.front();
        que.pop();
        int curX = curId % 100;
        int curY = curId / 100;
        int newX,newY;
        for (int i = 0; i < 4; ++i)
        {
            newX = curX + dsx1[i];
            newY = curY + dsy1[i];
            if (bound(newX,newY))
            {
                if (!visited[newY][newX])
                {    
                    if (Maps[newY][newX] == 'X')
                    {
                        visited[newY][newX] = true;
                        que.push(newY*100 + newX);
                    }
                    else
                    {
                        //add
                        ++ret;
                    }
                }
            }
            else
            {
                ++ret;
            }
        }
        for (int i = 0; i < 4; ++i)
        {
            newX = curX + dsx2[i];
            newY = curY + dsy2[i];
            if (bound(newX,newY))
            {
                if (!visited[newY][newX])
                {        
                    if (Maps[newY][newX] == 'X')
                    {
                        
                        visited[newY][newX] = true;
                        que.push(newY*100 + newX);
                    }
                }
            }
        }
    }
    return ret;
}

void Test()
{
    memset(Maps,0,sizeof(Maps));
    for (int i = 0; i < height; ++i)
    {
        scanf("%s",Maps[i]);
    }
    printf("%d\n",BFS());
}

int main()
{
    //freopen("data.txt","r",stdin);
    while(scanf("%d %d %d %d",&height,&width,&startY,&startX) != EOF)
    {
        if (height == 0)
        {
            break;
        }
        --startY;
        --startX;
        Test();
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator