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