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有更多的理解了1AC

Posted by gagagahahaxixi at 2015-11-07 12:18:09 on Problem 3009
#include <iostream>
#include <cstdio>
#define INF 0x3f3f3f3f
using namespace std;
const int MAX=22;

int map[MAX][MAX];
int  n,m;
int x1,y1,x2,y2;
int fx[]={1,-1,0,0};
int fy[]={0,0,1,-1};
int flag=0;
int step;
struct node
{
    int x,y;
}a;
bool move(int x,int y,int i)
{
    a.x=x,a.y=y;
    if(map[x][y]==3)
    {
        flag=1;
        a.x=x,a.y=y;
        return true;
    }
    if(x<1||x>n||y<1||y>m)
        return false;
    if(map[x][y]!=0)
        return false;
    while(1)
    {
        x+=fx[i];
        y+=fy[i];
        if(x<1||x>n||y<1||y>m)
            return false;
        if(map[x][y]==3)
        {

            flag=1;
            a.x=x,a.y=y;
            return true;
        }
        if(map[x][y]!=0)
        {
            return true;
        }

        a.x=x,a.y=y;
    }
}
void dfs(int x,int y,int ans)
{
    if(ans>10)
    {
        return ;
    }
    if(flag)
       {
           step=min(step,ans);
           return ;
       }

    for(int i=0;i<4;++i)
    {
        int tx=x+fx[i];
        int ty=y+fy[i];
        if(move(tx,ty,i)==false)
            continue;
        else
        {

            tx=a.x,ty=a.y;
            if(flag)
            {
//                printf("%d %d\n",step,ans);
                step=min(step,ans);
                return ;
            }
            map[tx+fx[i]][ty+fy[i]]=0;
//            for(int k=1;k<=n;++k)
//            {
//                for(int j=1;j<=m;++j)
//                    printf("%2d",map[k][j]);
//                printf("\n");
//            }
            dfs(tx,ty,ans+1);
            map[tx+fx[i]][ty+fy[i]]=1;
            flag=0;
        }
    }
}
int main()
{
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        if(m==0&&n==0)
            break;
        step=INF;
        flag=0;
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=m;++j)
            {
                scanf("%d",&map[i][j]);
                if(map[i][j]==2)
                {
                    x1=i,y1=j;
                    map[i][j]=0;
                }
                if(map[i][j]==3)
                {
                    x2=i,y2=j;
                }
            }
        }
        dfs(x1,y1,0);
        if(step!=INF&&step<=9)
            printf("%d\n",step+1);
        else
            printf("-1\n");
    }
    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