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 @
2008-07-25 15:23 小果子 閱讀(179) |
評論 (0) |
編輯 收藏DFS訓練題
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4
5 using namespace std;
6 vector<int> sticks;
7 int mark[25];
8 int s;
9 int dfs(int val,int h,int cnt)
10 {
11 for(int i=h;i<sticks.size();++i){
12 if(mark[i]==0){
13 mark[i]=1;
14 if(val+sticks[i]==s){
15 cnt++;
16 if(cnt==4)return 1;
17 int ans=dfs(0,1,cnt);
18 if(ans==1)return 1;
19 mark[i]=0;
20 return 0;
21 }
22 else if(val+sticks[i]<s){
23 int ans=dfs(val+sticks[i],i,cnt);
24 if(ans==1)return 1;
25 mark[i]=0;
26 }
27 else if(val+sticks[i]>s){
28 mark[i]=0;
29 return 0;
30 }
31 }
32 if(h>0&&mark[0]==0)return 0;
33 }
34 return 0;
35 }
36 int main()
37 {
38 int c;
39 scanf("%d",&c);
40 while(c--){
41 memset(mark,0,sizeof(mark));
42 sticks.clear();
43 int num;
44 int k;
45 scanf("%d",&k);
46 int sum=0;
47 int tmp=0;
48 while(k--){
49 scanf("%d",&num);
50 sticks.push_back(num);
51 sum+=num;
52 if(num>tmp)tmp=num;
53 }
54 if(sum%4!=0||sticks.size()<4){
55 printf("no\n");
56 continue;
57 }
58 s=sum/4;
59 if(s<tmp){
60 printf("no\n");
61 continue;
62 }
63 sort(sticks.begin(),sticks.end());
64 int ans=dfs(0,0,1);
65 if(ans){
66 printf("yes\n");
67 }
68 else printf("no\n");
69 }
70 return 0;
71 }
posted @
2008-07-24 20:56 小果子 閱讀(337) |
評論 (0) |
編輯 收藏 1 http://acm.hdu.edu.cn/showproblem.php?pid=1404 1 #include <iostream>
2 #include <sstream>
3 #include <string>
4
5 using namespace std;
6 const int N=1000000;
7 int dp[N];
8 int dfs(int n)
9 {
10 int hash[150];
11 memset(hash,0,sizeof(hash));
12 int tm,tp;
13 tm=tp=n;
14
15 tm=tp%10;
16 if(tm==0){
17 tp/=10;
18 if(dp[tp]==-1)
19 dp[tp]=dfs(tp);
20 hash[dp[tp]]=1;
21 }
22 while(tm>0){
23 --tp;
24 if(dp[tp]==-1)
25 dp[tp]=dfs(tp);
26 hash[dp[tp]]=1;
27 --tm;
28 }
29 tp=n;
30 tm=(tp/10)%10;
31 if(tm==0&&n>=100){
32 tp/=100;
33 if(dp[tp]==-1)
34 dp[tp]=dfs(tp);
35 hash[dp[tp]]=1;
36 }
37
38 while(tm>0){
39 tp-=10;
40 if(tp<10)break;
41 if(dp[tp]==-1)
42 dp[tp]=dfs(tp);
43 hash[dp[tp]]=1;
44 tm--;
45 }
46 tp=n;
47 tm=(tp/100)%10;
48 if(tm==0&&n>=1000){
49 tp/=1000;
50 if(dp[tp]==-1)
51 dp[tp]=dfs(tp);
52 hash[dp[tp]]=1;
53 }
54
55 while(tm>0){
56 tp-=100;
57 if(tp<100)break;
58 if(dp[tp]==-1)
59 dp[tp]=dfs(tp);
60 hash[dp[tp]]=1;
61 tm--;
62 }
63
64 tp=n;
65 tm=(tp/1000)%10;
66 if(tm==0&&n>=10000){
67 tp/=10000;
68 if(dp[tp]==-1)
69 dp[tp]=dfs(tp);
70 hash[dp[tp]]=1;
71 }
72 while(tm>0){
73 tp-=1000;
74 if(tp<1000)break;
75 if(dp[tp]==-1)
76 dp[tp]=dfs(tp);
77 hash[dp[tp]]=1;
78 tm--;
79 }
80
81 tp=n;
82 tm=(tp/10000)%10;
83 if(tm==0&&n>=100000){
84 tp/=100000;
85 if(dp[tp]==-1)
86 dp[tp]=dfs(tp);
87 hash[dp[tp]]=1;
88 }
89 while(tm>0){
90 tp-=10000;
91 if(tp<10000)break;
92 if(dp[tp]==-1)
93 dp[tp]=dfs(tp);
94 hash[dp[tp]]=1;
95 tm--;
96 }
97 tp=n;
98 tm=(tp/100000)%10;
99 while(tm>0){
100 tp-=100000;
101 if(tp<100000)break;
102 if(dp[tp]==-1)
103 dp[tp]=dfs(tp);
104 hash[dp[tp]]=1;
105 tm--;
106 }
107 for(int i=0;i<150;i++)
108 if(hash[i]==0)return i;
109 }
110
111 int main()
112 {
113 memset(dp,-1,sizeof(dp));
114 dp[0]=1;
115 char s[9];
116 while(gets(s)){
117 if(s[0]=='0'){
118 printf("Yes\n");
119 continue;
120 }
121 int len=strlen(s);
122 int nn=0;
123 for(int i=0;i<len;i++)
124 nn=nn*10+s[i]-48;
125 if(dp[nn]==-1)dp[nn]=dfs(nn);
126 if(dp[nn]==0){
127 printf("No\n");
128 }
129 else printf("Yes\n");
130 }
131 return 0;
132 }
讀入轉化為int用c++流處理比直接模擬轉化慢許多...一直TLE...以前沒怎么覺得慢...數據量大時估計就體現出來了...
posted @
2008-07-24 14:44 小果子 閱讀(429) |
評論 (0) |
編輯 收藏 http://acm.hdu.edu.cn/showproblem.php?pid=1524 1 #include <iostream>
2 #include <vector>
3
4 using namespace std;
5 int dp[1006];
6 struct Node
7 {
8 vector<int> next;
9 };
10 vector<Node> vec;
11 int dfs(int k)
12 {
13 int hash[100];
14 memset(hash,0,sizeof(hash));
15
16 for(int i=0;i<vec[k].next.size();++i){
17 if(dp[vec[k].next[i]]==-1)
18 dp[vec[k].next[i]]=dfs(vec[k].next[i]);
19 hash[dp[vec[k].next[i]]]=1;
20 }
21
22 for(int i=0;i<100;i++){
23 if(hash[i]==0)return i;
24 }
25 };
26 int main()
27 {
28 int n;
29 while(scanf("%d",&n)!=EOF){
30 vec.clear();
31 vec.resize(1005);
32 memset(dp,-1,sizeof(dp));
33 int k;
34 for(int i=0;i<n;i++){
35 scanf("%d",&k);
36 int a;
37 while(k--){
38 scanf("%d",&a);
39 vec[i].next.push_back(a);
40 }
41 }
42 int m;
43 while(scanf("%d",&m),m){
44 int sg=0;
45 for(int i=0;i<m;i++){
46 scanf("%d",&k);
47 if(dp[k]==-1)
48 dp[k]=dfs(k);
49 sg^=dp[k];
50 }
51 if(sg==0){
52 printf("LOSE\n");
53 }
54 else printf("WIN\n");
55 }
56 }
57 return 0;
58 }
59
posted @
2008-07-24 11:10 小果子 閱讀(359) |
評論 (0) |
編輯 收藏博弈的基礎題，通過求SG值，注意一點的是別忘了用記憶化搜索優化，否則容易TEL...
http://acm.hdu.edu.cn/showproblem.php?pid=1536
1 #include <iostream>
2 #include <algorithm>
3 #include <vector>
4 #include <bitset>
5
6 using namespace std;
7 vector<int> s;
8 int dp[10006];
9 int dfs(int v)
10 {
11 bitset<300> hash(0);
12 for(int i=0;i<s.size();i++){
13 if(v-s[i]>=0){
14 if(dp[v-s[i]]==-1){
15 dp[v-s[i]]=dfs(v-s[i]);
16 }
17 hash.set(dp[v-s[i]]);
18 }
19 else break;
20 }
21 for(int i=0;i<300;i++)
22 if(hash.test(i)==0)return i;
23 }
24
25 int main()
26 {
27 int k;
28 while(scanf("%d",&k)!=EOF,k){
29 s.clear();
30 s.reserve(105);
31 int n;
32 while(k--){
33 scanf("%d",&n);
34 s.push_back(n);
35 }
36 memset(dp,-1,sizeof(dp));
37 sort(s.begin(),s.end());
38 scanf("%d",&n);
39 while(n--){
40 int m;
41 int sg=0;
42 scanf("%d",&m);
43 while(m--){
44 int v;
45 scanf("%d",&v);
46 if(dp[v]==-1)
47 dp[v]=dfs(v);
48 sg^=dp[v];
49 }
50 printf(sg?"W":"L");
51 }
52 printf("\n");
53 }
54 return 0;
55 }
posted @
2008-07-23 20:54 小果子 閱讀(470) |
評論 (0) |
編輯 收藏