bfs的好題目！
開始想到用優(yōu)先隊(duì)列，無情的還是過了， 只不過時(shí)間用了2000ms多，差點(diǎn)就掛了~杯具的優(yōu)先
后來一想，其實(shí)可以直接bfs, 有情的是意料之外的沒有出現(xiàn)TE，而是AC，徹底無語的是只用了500ms多！！！！
大呼優(yōu)先之哀哉……
至于bfs的做法如下：
1，開始點(diǎn)進(jìn)棧
2，開始點(diǎn)能直接到達(dá)(不花時(shí)間的)的所有的點(diǎn)進(jìn)棧
3，分兩步
3.1 開始點(diǎn)不能直接到達(dá)（要時(shí)間）的點(diǎn)進(jìn)棧
3.2 將這個(gè)點(diǎn)能直接到達(dá)(不花時(shí)間的)的所有的點(diǎn)進(jìn)棧
3.3 跳轉(zhuǎn)到3
4 跳轉(zhuǎn)到1
注：開始點(diǎn)為當(dāng)前出棧的第一個(gè)點(diǎn)
不明白這個(gè)過程的可以看代碼（雖然代碼有點(diǎn)……，還可以進(jìn)一步簡化， 以后不能老想著優(yōu)先了，誰優(yōu)先誰杯具，當(dāng)然不是說我們的廣大女同胞……）
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4 struct node
5 {
6 int x, y, time;
7 /*friend bool operator < (node a, node b)
8 {
9 return a.time > b.time;
10 }*/
11 };
12 int n, m;
13 int xi[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
14 int yi[8] = {0, 1, 1, 1, 0, -1, -1, -1};
15 char map[1005][1005];
16 bool vist[1005][1005];
17 bool check(int dx, int dy)
18 {
19 if (dx >= 0 && dy >=0 && dx < n && dy < m) return true;
20 return false;
21 }
22 queue <node> q;
23 int bfs(node now, node end)
24 {
25 while (!q.empty())q.pop();
26 now.time = 0;
27 q.push(now);
28
29 for (int i = 0; i < n; i++)
30 for (int j = 0; j < m; j++)
31 vist[i][j] = false;
32 vist[now.x][now.y] = true;
33 node next, tmp;
34 bool flag = false;
35 while (!q.empty())
36 {
37 now = q.front();
38 tmp = now;
39 if (now.x == end.x && now.y == end.y) return now.time;
40 q.pop();
41 flag = false;
42 while (1)
43 {
44 next.x = tmp.x + xi[map[tmp.x][tmp.y]-'0'];
45 next.y = tmp.y + yi[map[tmp.x][tmp.y]-'0'];
46 if (check(next.x, next.y) && !vist[next.x][next.y])
47 {
48 if (next.x == end.x && next.y == end.y) return tmp.time;
49 next.time = tmp.time;
50 vist[next.x][next.y] = true;
51 q.push(next);
52 tmp = next;
53 }else break;
54 }
55 for (int i = 0; i < 8; i++)
56 {
57 next.x = now.x + xi[i];
58 next.y = now.y + yi[i];
59 if (check(next.x, next.y) && !vist[next.x][next.y])
60 {
61 if (map[now.x][now.y] - '0' == i) next.time = now.time;
62 else next.time = now.time + 1;
63 if (next.x == end.x && next.y == end.y) return next.time;
64 vist[next.x][next.y] = true;
65 q.push(next);
66 tmp = next;
67 while (1)
68 {
69 next.x = tmp.x + xi[map[tmp.x][tmp.y]-'0'];
70 next.y = tmp.y + yi[map[tmp.x][tmp.y]-'0'];
71 if (check(next.x, next.y) && !vist[next.x][next.y])
72 {
73 if (next.x == end.x && next.y == end.y) return tmp.time;
74 next.time = tmp.time;
75 vist[next.x][next.y] = true;
76 q.push(next);
77 tmp = next;
78 }else break;
79 }
80 }
81 }
82 }
83 return 0;
84 }
85 int main()
86 {
87 while (scanf("%d%d", &n, &m) != EOF)
88 {
89 int i, j;
90 for (i = 0; i < n; i++)
91 scanf("%s", map[i]);
92 int T;
93 scanf("%d", &T);
94 node now, end;
95 for (i = 0; i < T; i++)
96 {
97 scanf("%d%d%d%d", &now.x, &now.y, &end.x, &end.y);
98 now.time = 0;
99 now.x --;
100 now.y --;
101 end.x --;
102 end.y --;
103 if (now.x == end.x && now.y == end.y)
104 {
105 printf("0\n");
106 }else printf("%d\n", bfs(now, end));
107 }
108 }
109 return 0;
110 }
111
posted @
2012-04-22 20:23 路修遠(yuǎn) 閱讀(1337) |
評(píng)論 (0) |
編輯 收藏
單純的bfs()，當(dāng)然你也可以用dfs,只要你不怕超時(shí)或者你的剪枝夠強(qiáng)大
最好開一個(gè)三維的數(shù)組，記錄每一個(gè)格子的每一個(gè)方向上的最小值，直到bfs完成
具體看代碼，不做過多的解釋。
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4 struct node
5 {
6 int x, y;
7 int step, dir;
8 };
9 int n, m;
10 int xi[4] = {0, 1, -1, 0};
11 int yi[4] = {1, 0, 0, -1};
12 int vist[82][82][4];
13 char map[82][82];
14 node start;
15 queue <node> q;
16 bool check(int dx, int dy)
17 {
18 if(dx >= 1 && dx <= n && dy >= 1 && dy <= m) return true;
19 else return false;
20 }
21 bool find(node a)
22 {
23 if ((a.x == 1 || a.x == n || a.y == 1 || a.y == m)) return true;
24 else return false;
25 }
26 int bfs()
27 {
28 while (!q.empty())q.pop();
29 memset(vist, 0, sizeof(vist));
30 start.dir = -1;
31 start.step = 0;
32 q.push(start);
33 node now, next;
34 bool flag = true;
35 int tmp;
36 while (!q.empty())
37 {
38 now = q.front();
39 q.pop();
40 if (find(now)) return now.step;
41
42 flag = false;
43 for (int i = 0 ; i < 4; i++)
44 {
45 if (now.dir == i) continue;
46 if (now.dir >=0 && 3-now.dir == i) continue;
47 next.x = now.x + xi[i];
48 next.y = now.y + yi[i];
49 next.step = now.step + 1;
50 if (check(next.x, next.y) && map[next.x][next.y] == '.' )
51 {
52 if (vist[next.x][next.y][i] == 0)
53 {
54 vist[next.x][next.y][i] = next.step;
55 next.dir = i;
56 q.push(next);
57 }
58 else if (vist[next.x][next.y][i] > next.step)
59 {
60 vist[next.x][next.y][i] = next.step;
61 next.dir = i;
62 q.push(next);
63 }
64 flag = true;
65 }
66 }
67 if (!flag)
68 {
69 int i = now.dir;
70 if (i < 0) return 0;
71 next.x = now.x + xi[i];
72 next.y = now.y + yi[i];
73 next.step = now.step + 1;
74 if (check(next.x, next.y) && map[next.x][next.y] == '.' )
75 {
76 if (vist[next.x][next.y][i] == 0)
77 {
78 vist[next.x][next.y][i] = next.step;
79 next.dir = i;
80 q.push(next);
81 }
82 else if (vist[next.x][next.y][i] > next.step)
83 {
84 vist[next.x][next.y][i] = next.step;
85 next.dir = i;
86 q.push(next);
87 }
88 flag = true;
89 }
90 }
91 }
92 return -1;
93 }
94 int main()
95 {
96 int cas;
97 scanf("%d", &cas);
98 while (cas--)
99 {
100 scanf("%d%d", &n, &m);
101 int i, j;
102 for (i = 1; i <= n; i++)
103 scanf("%s", map[i]+1);
104 for (i = 1; i <= n; i++)
105 for (j = 1; j <= m; j++)
106 {
107 if (map[i][j] == '@')
108 {
109 start.x = i;
110 start.y = j;
111 map[i][j] = '.';
112 }
113 }
114 int ans = bfs();
115 printf("%d\n", ans);
116 }
117 return 0;
118 }
119
posted @
2012-04-13 18:34 路修遠(yuǎn) 閱讀(1312) |
評(píng)論 (0) |
編輯 收藏
題目大意：
去掉給定的邊，看每一個(gè)點(diǎn)是否能從別的點(diǎn)到達(dá)！
如果能夠到達(dá)，則求出對(duì)于每一個(gè)點(diǎn)到其他所有的點(diǎn)最短距離之和，將這些和相加就是最后的結(jié)果
解題思路：
對(duì)每一個(gè)點(diǎn)求一次單源最短路，然后求和，相加的到最后的結(jié)果……
但，算一下時(shí)間復(fù)雜度： 復(fù)雜度是O(M*N*M)。由于M*N*M=3000*100*3000=9*10
8，不可能AC
所以，需要我們另辟他徑。網(wǎng)上有說建什么最短路徑樹，這個(gè)我不懂……
我的思路是：引用前面的思路，對(duì)每一個(gè)點(diǎn)求一次最短路，并將其求和，保存在一個(gè)數(shù)組里頭，定為sum[i]，i表示著一個(gè)點(diǎn)到所有其他點(diǎn)最短路之和。并將這些和相加 ans = sum[1] + …… + sum[n];
然后，刪除一條邊，其頂點(diǎn)暫定為u,v，對(duì)這條邊的一個(gè)頂點(diǎn)u在一次求最短路，如果這個(gè)點(diǎn)，不能到達(dá)這條邊的另一個(gè)點(diǎn)v，則 直接輸出INF
如果，能夠到達(dá)，則對(duì)v也求一次最短路，對(duì)于u，v兩點(diǎn)來說，求得u到每一個(gè)點(diǎn)的最短路之和sum_u，求得v到每一個(gè)點(diǎn)的最短路之和sum_v，
最后結(jié)果為： ans = ans + sum_u + sum_v - sum[u] - sum[v];
ans為最后答案（千萬記住是每一組的，因?yàn)橛衜條邊）
具體看代碼：
http://acm.hdu.edu.cn/showproblem.php?pid=2433時(shí)間是 953ms
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4 const int SIZE = 102;
5 const int INF = 1 << 30;
6 struct node
7 {
8 int v, w, next;
9 }map[SIZE * SIZE];
10
11 int head[SIZE], use;
12 int num[SIZE * 30];
13 int sum[SIZE];
14
15 void add(int u, int v, int w)
16 {
17 map[use].v = v;
18 map[use].w = w;
19 map[use].next = head[u];
20 head[u] = use ++;
21 }
22 void init()
23 {
24 use = 0;
25 memset(head, -1, sizeof(head));
26 memset(sum, 0, sizeof(sum));
27 }
28
29 queue <int> q;
30 bool vist[SIZE];
31 int dis[SIZE];
32
33 int spfa(int s)
34 {
35 while (!q.empty()) q.pop();
36
37 for (int i = 0; i < SIZE ; i ++) dis[i] = INF;
38
39 memset(vist, false, sizeof(vist));
40 dis[s] = 0;
41 vist[s] = true;
42 q.push(s);
43 int ans = 0;
44 while (!q.empty())
45 {
46 int u = q.front();
47 q.pop();
48 vist[u] = false;
49 ans += dis[u];
50 for (int i = head[u]; i != -1; i = map[i].next)
51 {
52 int v = map[i].v;
53 if (dis[v] > dis[u] + map[i].w)
54 {
55 dis[v] = dis[u] + map[i].w;
56 if (!vist[v])
57 {
58 vist[v] = true;
59 q.push(v);
60 }
61 }
62 }
63 }
64 return ans;
65 }
66 int main()
67 {
68 int n, m;
69 while (scanf("%d%d", &n, &m) != EOF)
70 {
71 int i, j, k;
72 int u, v;
73 init();
74 memset(num, 0, sizeof(num));
75 for (i = 1; i <= m; i++)
76 {
77 scanf("%d%d", &u, &v);
78 num[i] = use;
79 add(u, v, 1);
80 add(v, u, 1);
81 }
82 int ans = 0;
83 for (i = 1; i <= n; i++)
84 {
85 sum[i] = spfa(i);
86 ans += sum[i];
87 }
88 int tmp = ans;
89 for (i = 1; i <= m; i++)
90 {
91 map[num[i]].w = INF;
92 map[num[i]^1].w = INF;
93
94 ans = tmp;
95 ans += spfa(map[num[i]].v);
96
97 if (dis[map[num[i]^1].v] == INF)
98 {
99 printf("INF\n");
100 }
101 else
102 {
103 ans += spfa(map[num[i]^1].v);
104 ans = ans - sum[map[num[i]].v] - sum[map[num[i]^1].v];
105 printf("%d\n", ans);
106 }
107 map[num[i]].w = 1;
108 map[num[i]^1].w = 1;
109 }
110 }
111 return 0;
112 }
113
posted @
2012-03-09 15:35 路修遠(yuǎn) 閱讀(1876) |
評(píng)論 (8) |
編輯 收藏 Going Home
Description
On a grid map there are n little men and n houses. In each unit time, every little man can move one unit step, either horizontally, or vertically, to an adjacent point. For each little man, you need to pay a $1 travel fee for every step he moves, until he enters a house. The task is complicated with the restriction that each house can accommodate only one little man.
Your task is to compute the minimum amount of money you need to pay in order to send these n little men into those n different houses. The input is a map of the scenario, a '.' means an empty space, an 'H' represents a house on that point, and am 'm' indicates there is a little man on that point.
You can think of each point on the grid map as a quite large square, so it can hold n little men at the same time; also, it is okay if a little man steps on a grid with a house without entering that house.
Input
There are one or more test cases in the input. Each case starts with a line giving two integers N and M, where N is the number of rows of the map, and M is the number of columns. The rest of the input will be N lines describing the map. You may assume both N and M are between 2 and 100, inclusive. There will be the same number of 'H's and 'm's on the map; and there will be at most 100 houses. Input will terminate with 0 0 for N and M.
Output
For each test case, output one line with the single integer, which is the minimum amount, in dollars, you need to pay.
Sample Input
2 2
.m
H.
5 5
HH..m
.....
.....
.....
mm..H
7 8
...H....
...H....
...H....
mmmHmmmm
...H....
...H....
...H....
0 0
Sample Output
2
10
28
KM算法！
其實(shí)這個(gè)題求的是最小權(quán)匹配，，但有些題目最小不一定好求，于是我們可以換一種思維，將有所的距離變成負(fù)的，那么我們要求的就是最大權(quán)匹配！（在一位大牛的指點(diǎn)下）
廢話不多說，看程序：
1 #include<iostream>
2 using namespace std;
3 #define Inf 10000000;
4 int map[105][105];
5 int slack[105];
6 int lx[105],ly[105];
7 bool x[105],y[105];
8 int link[105];
9 int n,m;
10 char mm[105][105];
11 bool dfs(int v)
12 {
13 x[v]=true;
14 int t;
15 for (int i=0;i<m;i++)
16 {
17 if (!y[i])
18 {
19 t=lx[v]+ly[i]-map[v][i];
20 if (t==0)
21 {
22 y[i]=true;
23 if (link[i]==-1||dfs(link[i]))
24 {
25 link[i]=v;
26 return true;
27 }
28 }
29 else slack[i]=min(slack[i],t);
30 }
31 }
32 return false;
33 }
34 void KM()
35 {
36 int i,j,k;
37 memset(link,-1,sizeof(link));
38 for (i=0;i<=m;i++)
39 {
40 lx[i]=-Inf;
41 ly[i]=0;
42 }
43 for (i=0;i<m;i++)
44 {
45 while (1)
46 {
47 memset(x,0,sizeof(x));
48 memset(y,0,sizeof(y));
49
50 for (j=0;j<m;j++) slack[j]=Inf;
51
52 if (dfs(i))break;
53
54 int d=Inf;
55 for (j=0;j<m;j++)
56 if (!y[j])d=min(slack[j],d);
57
58 for (j=0;j<m;j++)
59 {
60 if (x[j])lx[j]-=d;
61 if (y[j])ly[j]+=d;
62 }
63 for (j=0;j<m;j++)
64 if (!y[j])slack[j]-=d;
65 }
66 }
67 }
68 int main()
69 {
70 int i,j,k,t,l,v;
71 while (cin>>k>>t)
72 {
73 if (k+t==0)break;
74 for (i=1;i<=k;i++)
75 for (j=1;j<=t;j++)
76 scanf(" %c",&mm[i][j]);
77 memset(map,0,sizeof(map));
78 n=0,m=0;
79 for (i=1;i<=k;i++)
80 for (j=1;j<=t;j++)
81 {
82 if (mm[i][j]=='H')
83 {
84 n=0;
85 for (l=1;l<=k;l++)
86 for (v=1;v<=t;v++)
87 {
88 if (mm[l][v]=='m')
89 {
90 map[m][n]=-(abs(i-l)+abs(j-v));
91 n++;
92 }
93 }
94 m++;
95 }
96 }
97 KM();
98 int sum=0;
99 for (i=0;i<m;i++)
100 sum+=map[link[i]][i];
101 cout<<0-sum<<endl;
102 }
103 return 0;
104 }
105
106
posted @
2011-04-19 13:54 路修遠(yuǎn) 閱讀(1436) |
評(píng)論 (0) |
編輯 收藏
摘要:
閱讀全文
posted @
2011-04-05 10:46 路修遠(yuǎn) 閱讀(1347) |
評(píng)論 (0) |
編輯 收藏沒什么好說的，直接匈牙利算法
#include<iostream>
using namespace std;
int n,m;//n為x集合，m為y集合
int map[305][305];//map[x][y]表示x,y兩點(diǎn)之間有邊相連
bool visit[305];//記錄m中的i節(jié)點(diǎn)是否被訪問過
int link[305];//記錄當(dāng)前n中的i節(jié)點(diǎn)是否與 j節(jié)點(diǎn)相連
bool dfs(int a)
{
int i;
for (i=1;i<=n;i++)
{
if (map[a][i]&&!visit[i])
{
visit[i]=true;
if (link[i]==0||dfs(link[i]))
{
link[i]=a;
return true;
}
}
}
return false;
}
int find()
{
int sum=0;
for (int i=1;i<=n;i++)
{
memset(visit,0,sizeof(visit));
if (dfs(i))sum++;
}
return sum;//最大匹配數(shù)
}
int main()
{
int t,i,j,k,x;
while (scanf("%d%d",&n,&m)!=EOF)
{
memset(map,0,sizeof(map));
memset(link,0,sizeof(link));
for (i=1;i<=n;i++)
{
scanf("%d",&j);
for (k=1;k<=j;k++)
{
scanf("%d",&x);
map[i][x]=1;
}
}
cout<<find()<<endl;
}
return 0;
}
posted @
2011-04-04 09:50 路修遠(yuǎn) 閱讀(1259) |
評(píng)論 (0) |
編輯 收藏其實(shí)這個(gè)題，和我上次講的那個(gè)連連看一樣！只不過是字符變成了整型而已！
還是貼一下關(guān)鍵代碼吧(⊙o⊙)~~
1 bool search(int x1,int y1,int x2,int y2,int n,int m)
2 {
3 memset(gk,0,sizeof(gk));
4 int t=game[x2][y2];
5 game[x2][y2]=0;
6 gk[x1][y1]=1;
7
8 //對(duì)game[x1][y1]四個(gè)方向是空格的標(biāo)為1
9 for (int i=x1-1;i>=1;i--)
10 {
11 if(game[i][y1]==0)gk[i][y1]=1;
12 else break;
13 }
14 for (int j=x1+1;j<=n;j++){
15 if(game[j][y1]==0)gk[j][y1]=1;
16 else break;
17 }
18
19 for (int i=y1-1;i>=1;i--){
20 if(game[x1][i]==0)gk[x1][i]=1;
21 else break;
22 }
23 for (int i=y1+1;i<=m;i++){
24 if(game[x1][i]==0)gk[x1][i]=1;
25 else break;
26 }
27
28 if (gk[x2][y2]>0&&gk[x2][y2]<4)
29 {
30 game[x2][y2]=t;
31 return true;
32 }
33 //對(duì)gk[i][j]為1的四個(gè)方向是空格的標(biāo)為2
34 for (int i=1;i<=n;i++)
35 for (int j=1;j<=m;j++)
36 if (gk[i][j]==1)
37 {
38 for (int k=i-1;k>=1;k--)
39 {
40 if (game[k][j]==0){
41 if(gk[k][j]==0)gk[k][j]=2;
42 }
43 else break;
44 }
45 for (int k=i+1;k<=n;k++){
46 if (game[k][j]==0){
47 if(gk[k][j]==0)gk[k][j]=2;
48 }
49 else break;
50 }
51
52 for (int k=j-1;k>=1;k--){
53 if (game[i][k]==0){
54 if(gk[i][k]==0)gk[i][k]=2;
55 }
56 else break;
57 }
58 for (int k=j+1;k<=m;k++){
59 if (game[i][k]==0){
60 if(gk[i][k]==0)gk[i][k]=2;
61 }
62 else break;
63 }
64 }
65
66 if (gk[x2][y2]>0&&gk[x2][y2]<4)
67 {
68 game[x2][y2]=t;
69 return true;
70 }
71 //對(duì)gk[i][j]為2的四個(gè)方向是空格的標(biāo)為3
72 for (int i=1;i<=n;i++)
73 for (int j=1;j<=m;j++)
74 if (gk[i][j]==2){
75 for (int k=i-1;k>=1;k--)
76 {
77 if (game[k][j]==0)
78 {
79 if(gk[k][j]==0)gk[k][j]=3;
80 }
81 else break;
82 }
83 for (int k=i+1;k<=n;k++)
84 {
85 if (game[k][j]==0)
86 {
87 if(gk[k][j]==0)gk[k][j]=3;
88 }
89 else break;
90 }
91
92 for (int k=j-1;k>=1;k--)
93 {
94 if (game[i][k]==0){
95 if(gk[i][k]==0)gk[i][k]=3;
96 }
97 else break;
98 }
99 for (int k=j+1;k<=m;k++)
100 {
101 if (game[i][k]==0)
102 {
103 if(gk[i][k]==0)gk[i][k]=3;
104 }
105 else break;
106 }
107 }
108
109 game[x2][y2]=t;
110 if(gk[x2][y2]>0&&gk[x2][y2]<4)return true;
111 if(gk[x2][y2]==0) return false;
112 }
posted @
2010-11-24 16:07 路修遠(yuǎn) 閱讀(1815) |
評(píng)論 (0) |
編輯 收藏
其實(shí)這個(gè)題是一個(gè)簡單的搜索問題，理解了很好做！注意4代表時(shí)間復(fù)原就行了！具體的在程序里頭，這里就不多說了，深知多說無益，還是要多練的！
1 #include<iostream>
2 using namespace std;
3 int map[12][12],tp[12][12],tt[12][12];
4 int n,m;
5 int Min=0xffffff,sum=0;
6 int x[4]={1,0,0,-1};
7 int y[4]={0,1,-1,0};
8 bool f=true;
9 //數(shù)組的交換
10 void fun(int a[12][12],int b[12][12])
11 {
12 for (int i=1;i<=n;i++)
13 for (int j=1;j<=n;j++)
14 a[i][j]=b[i][j];
15
16 }
17 void dfs(int x1,int y1,int sum,int p)
18 {
19 if(map[x1][y1]==3&&p>=0)
20 {
21 // 這里要注意，我是從5開始的，搜到3時(shí)，p應(yīng)該是0以上，
22 //剛開始是沒搞清楚，p大于0,wa了幾次，就是沒找到錯(cuò)誤！
23 if(Min>sum)Min=sum;
24 //cout<<sum<<endl;
25 f=false;
26 return;
27 }
28 int dx,dy;
29 for (int i=0;i<4;i++)
30 {
31 dx=x1+x[i]; dy=y1+y[i];
32 if (map[dx][dy]!=0&&tp[dx][dy]==0&&p>=1)
33 {
34 if(map[dx][dy]==4)
35 {
36 map[dx][dy]=0;
37 int temp=p;
38 p=5;
39 // cout<<p<<' '<<dx<<' '<<dy<<endl;
40 //輸出路徑，偏于查找當(dāng)前的坐標(biāo)位置和剩余時(shí)間p
41 fun(tt,tp);
42 memset(tp,0,sizeof(tp));
43 //到4是可以往回搜的，所以前面的走過的路徑應(yīng)該移除標(biāo)記
44 //用數(shù)組tt記住前面走過的路徑，以便于后面的搜索
45 tp[dx][dy]=1;
46 dfs(dx,dy,sum+1,p);
47 //出來混的，是要還的！這里也一樣！
48 map[dx][dy]=4;
49 tp[dx][dy]=0;
50 p=temp;
51 fun(tp,tt);
52 }
53 else
54 {
55 tp[dx][dy]=1;
56 //cout<<"->"<<p<<' '<<dx<<' '<<dy<<endl;
57 //輸出路徑，偏于查找當(dāng)前的坐標(biāo)位置和剩余時(shí)間p
58 dfs(dx,dy,sum+1,p-1);
59 tp[dx][dy]=0;
60 }
61 }
62 }
63 }
64 int main()
65 {
66 int t;
67 cin>>t;
68 while (t--)
69 {
70 memset(map,0,sizeof(map));
71 memset(tp,0,sizeof(tp));
72 cin>>n>>m;
73 f=true;
74 int x1,y1,x2,y2;
75 for (int i=1;i<=n;i++)
76 for (int j=1;j<=m;j++)
77 {
78 cin>>map[i][j];
79 if(map[i][j]==2)x1=i,y1=j;
80 //if(map[i][j]==3)x2=i,y2=j;
81 }
82 Min=0xffffff,sum=0;
83 int p=5;
84 map[x1][y1]=0;
85 dfs(x1,y1,sum,5);
86 if(!f)cout<<Min<<endl;
87 else cout<<-1<<endl;
88 }
89 return 0;
90 }
91
posted @
2010-11-09 16:59 路修遠(yuǎn) 閱讀(1497) |
評(píng)論 (0) |
編輯 收藏“九宮填數(shù)“也叫“九方數(shù)”，古代稱為“九宮算”。九宮填數(shù)是將九個(gè)有效數(shù)字填在九個(gè)方位格子里，要使每行、每列和每條對(duì)角線上的和都相等，即：橫的三個(gè)數(shù)之和、豎的三個(gè)數(shù)之和與斜的三個(gè)數(shù)之和，都相等。在解這個(gè)題之前，先把九宮的方位問題明確了，以便講行具體的闡述。
這個(gè)方位的確定與看地圖的方位是一致的。由于要把1—9這九個(gè)數(shù)填在適當(dāng)?shù)母褡永铮@九個(gè)數(shù)之和是45，無論是橫、豎、斜都是三個(gè)數(shù)，把45平均分成三行，每行三個(gè)數(shù)的和都是15（包括橫、豎、斜）。每三個(gè)數(shù)的情況：橫有3種，豎有3種，斜有2種，共8種。
只要知道三個(gè)數(shù)就可以枚舉所有的數(shù)了；
1 #include<iostream>
2 using namespace std;
3 int b[10],a[10];
4 int main(){
5 int f = 0;
6 for (int i=1;i<10;i++){
7 if(i!=5)b[1]=i;
8 for (int j=1;j<10;j++)
9 {
10 b[5] = 5;
11 if(j!=i&&j!=5&&i!=5){
12 b[2] = j;
13 b[8] = 15 - b[2] - b[5];
14 b[3] = 15 - b[1] - b[2];
15 b[9] = 15 - b[1] - b[5];
16 b[7] = 15 - b[3] - b[5];
17 b[4] = 15 - b[1] - b[7];
18 b[6] = 15 - b[3] - b[9];
19 if(b[4]+b[5]+b[6]==15&&b[7]+b[8]+b[9]==15)
20 {
21 f = 0;
22 memset(a,0,sizeof(a));
23 for (int k=1;k<10;k++) a[b[k]]++;
24 for (int k=1;k<10;k++) if(a[k]<=0||a[k]>1){f = 1;break;}
25 if(f==0){
26 for (int k=1;k<10;k++)
27 {
28 cout<< b[k] <<' ';
29 if(k%3==0)cout << endl;
30 }
31 cout << endl;
32 }
33 }
34 }
35 }
36 }
37 system("pause");
38 return 0;
39 }
40
posted @
2010-06-30 08:14 路修遠(yuǎn) 閱讀(489) |
評(píng)論 (0) |
編輯 收藏Problem Description
RSA is one of the most powerful methods to encrypt data. The RSA algorithm is described as follow:
> choose two large prime integer p, q
> calculate n = p × q, calculate F(n) = (p - 1) × (q - 1)
> choose an integer e(1 < e < F(n)), making gcd(e, F(n)) = 1, e will be the public key
> calculate d, making d × e mod F(n) = 1 mod F(n), and d will be the private key
You can encrypt data with this method :
C = E(m) = me mod n
When you want to decrypt data, use this method :
M = D(c) = cd mod n
Here, c is an integer ASCII value of a letter of cryptograph and m is an integer ASCII value of a letter of plain text.
Now given p, q, e and some cryptograph, your task is to "translate" the cryptograph into plain text.
Input
Each case will begin with four integers p, q, e, l followed by a line of cryptograph. The integers p, q, e, l will be in the range of 32-bit integer. The cryptograph consists of l integers separated by blanks.
Output
For each case, output the plain text in a single line. You may assume that the correct result of plain text are visual ASCII letters, you should output them as visualable letters with no blank between them.
Sample Input
101 103 7 11
7716 7746 7497 126 8486 4708 7746 623 7298 7357 3239
Sample Output
I-LOVE-ACM.
以為要數(shù)組，想想，不是那么回事！
挺簡單的~~
1 #include<iostream>
2 using namespace std;
3 int main(){
4 int p,q,e,t;
5 while (cin>>p>>q>>e>>t)
6 {
7 int n = p*q,fn = (p-1)*(q-1);
8 int d =1;
9 while ((d*e)%fn!=1)d++;
10 int c;
11 for (int i=0;i<t;i++)
12 {
13 cin>>c;
14 int temp=1;
15 for (int j=1;j<=d;j++)
16 {
17 temp*=c;
18 temp%=n;
19 }
20 cout<<char(temp);
21 }
22 cout<<endl;
23 }
24 return 0;
25 }
posted @
2010-06-26 18:59 路修遠(yuǎn) 閱讀(465) |
評(píng)論 (0) |
編輯 收藏