| ||||||||||
| 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 | |||||||||
DFS,63MS。。。#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator