http://acm.pku.edu.cn/JudgeOnline/problem?id=3669problem: to find a position which is safe before T time in the first quadrant.Or output -1...
BFS...
1 #include <iostream>
2 #include <vector>
3 #include <queue>
4
5 using namespace std;
6 struct Node
7 {
8 int xi,yi;
9 int time;
10 Node(int x=0,int y=0,int t=0):xi(x),yi(y),time(t){};
11 };
12 int mark[305][305];
13 int load[305][305];
14 int dir[4][2]={1,0,-1,0,0,1,0,-1};
15 int n;
16 void Input()
17 {
18 int x,y,t;
19 memset(mark,-1,sizeof(mark));
20 memset(load,0,sizeof(load));
21 for(int i=0;i<n;i++){
22 scanf("%d%d%d",&x,&y,&t);
23 if(mark[x][y]>t||mark[x][y]==-1)mark[x][y]=t;
24 if(x-1>=0){
25 if(mark[x-1][y]>t||mark[x-1][y]==-1)mark[x-1][y]=t;
26 }
27 if(y-1>=0){
28 if(mark[x][y-1]>t||mark[x][y-1]==-1)mark[x][y-1]=t;
29 }
30 if(mark[x+1][y]>t||mark[x+1][y]==-1)mark[x+1][y]=t;
31 if(mark[x][y+1]>t||mark[x][y+1]==-1)mark[x][y+1]=t;
32 }
33 }
34 inline bool BFS()
35 {
36 queue<Node> que;
37 Node start(0,0,0);
38 load[0][0]=1;
39 if(mark[0][0]==-1){
40 printf("0\n");
41 return true;
42 }
43 que.push(start);
44 while(!que.empty()){
45 Node tmp=que.front();
46 que.pop();
47 for(int i=0;i<4;i++){
48 int xi=tmp.xi+dir[i][0];
49 int yi=tmp.yi+dir[i][1];
50 int t=tmp.time+1;
51 if(xi<0||yi<0)continue;
52 if(mark[xi][yi]<=t&&mark[xi][yi]!=-1)continue;
53 if(load[xi][yi])continue;
54 if(mark[xi][yi]==-1){
55 printf("%d\n",t);
56 return true;
57 }
58 Node tt(xi,yi,t);
59 load[xi][yi]=1;
60 que.push(tt);
61 }
62 }
63 return false;
64 }
65 int main()
66 {
67 while(scanf("%d",&n)!=EOF){
68 Input();
69 if(BFS()==false){
70 printf("-1\n");
71 }
72 }
73 return 0;
74 }
posted on 2008-07-25 15:23
小果子 閱讀(183)
評論(0) 編輯 收藏 引用