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

DFS,63MS。。。

Posted by makuiyu at 2013-10-24 20:05:46 on Problem 3009
#include <algorithm>
#include <iostream>
#include <string>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>

#define N 30

using namespace std;

struct point
{
    int x, y;
};

int map[N][N];
int w, h, steps;
point s;
int move[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

void DFS(point p, int step)
{
    for(int i=0; i<4; ++i)
    {
        point temp, temp2;
        temp.x = p.x + move[i][0];
        temp.y = p.y + move[i][1];
        if(step<steps-1 && temp.x>=0 && temp.x<h && temp.y>=0 && temp.y<w &&
           map[temp.x][temp.y]!=1)
        {
            while(temp.x>=0 && temp.x<h && temp.y>=0 && temp.y<w &&
                  map[temp.x][temp.y]==0)
            {
                temp.x += move[i][0];
                temp.y += move[i][1];
            }

            temp2.x = temp.x - move[i][0];
            temp2.y = temp.y - move[i][1];

            if(temp.x>=0 && temp.x<h && temp.y>=0 && temp.y<w)
            {
                if(map[temp.x][temp.y] == 3)
                    steps = step+1;
                if(map[temp.x][temp.y] == 1)
                {
                    map[temp.x][temp.y] = 0;
                    DFS(temp2, step+1);
                    map[temp.x][temp.y] = 1;
                }
            }
        }
    }
}

int main()
{
    int i, j;
    while(scanf("%d %d", &w, &h) != EOF)
    {
        if(w==0 && h==0)
            break;
        steps = 11;
        for(i=0; i<h; ++i)
            for(j=0; j<w; ++j)
            {
                scanf("%d", &map[i][j]);
                if(map[i][j] == 2)
                {
                    s.x = i;
                    s.y = j;
                    map[i][j] = 0;
                }
            }
        DFS(s, 0);
        printf("%d\n", steps<11?steps:-1);
    }
    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