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

留念~判断步数的没放对位置超时了两次。。。。

Posted by w201593121 at 2016-03-22 19:34:03 on Problem 3009
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
const int N=20+1;
using namespace std;
int mapp[N][N],vis[N][N],step,ans,w,h;
int dx[4]= {1,0,-1,0},dy[4]= {0,1,0,-1};
void dfs(int step,int x,int y)
{
    if(mapp[x][y]==3)ans=min(ans,step);
    else
    {
        if(step<10)
        {
            for(int i=0; i<4; i++)
                for(int j=1;; j++)
                {
                    if(0<=x+j*dx[i]&&x+j*dx[i]<h&&0<=y+j*dy[i]&&y+j*dy[i]<w&&mapp[x+dx[i]][y+dy[i]]!=1)
                    {
                        if(mapp[x+j*dx[i]][y+j*dy[i]]==1)
                        {
                            mapp[x+j*dx[i]][y+j*dy[i]]=0;
                            dfs(step+1,x+(j-1)*dx[i],y+(j-1)*dy[i]);
                            mapp[x+j*dx[i]][y+j*dy[i]]=1;
                            break;
                        }
                        else if(mapp[x+j*dx[i]][y+j*dy[i]]==3)
                        {
                            dfs(step+1,x+j*dx[i],y+j*dy[i]);
                            break;
                        }
                    }
                    else break;
                }
        }
    }
}
int main()
{
    int x0,y0;
    while(cin>>w>>h&&(w+h))
    {
        ans=0x3f3f3f3f;
        memset(mapp,-1,sizeof(mapp));
        for(int i=0; i<h; i++)
            for(int j=0; j<w; j++)
            {
                cin>>mapp[i][j];
                if(mapp[i][j]==2)
                {
                    x0=i;
                    y0=j;
                    mapp[i][j]=0;
                }
            }
        dfs(0,x0,y0);
        if(ans<=10)cout<<ans<<endl;
        else cout<<-1<<endl;
    }
}

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