| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
留念~判断步数的没放对位置超时了两次。。。。#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator