bfs的好題目！
開始想到用優先隊列，無情的還是過了， 只不過時間用了2000ms多，差點就掛了~杯具的優先
后來一想，其實可以直接bfs, 有情的是意料之外的沒有出現TE，而是AC，徹底無語的是只用了500ms多！！！！
大呼優先之哀哉……
至于bfs的做法如下：
1，開始點進棧
2，開始點能直接到達(不花時間的)的所有的點進棧
3，分兩步
3.1 開始點不能直接到達（要時間）的點進棧
3.2 將這個點能直接到達(不花時間的)的所有的點進棧
3.3 跳轉到3
4 跳轉到1
注：開始點為當前出棧的第一個點
不明白這個過程的可以看代碼（雖然代碼有點……，還可以進一步簡化， 以后不能老想著優先了，誰優先誰杯具，當然不是說我們的廣大女同胞……）
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 路修遠 閱讀(1350) |
評論 (0) |
編輯 收藏
單純的bfs()，當然你也可以用dfs,只要你不怕超時或者你的剪枝夠強大
最好開一個三維的數組，記錄每一個格子的每一個方向上的最小值，直到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 路修遠 閱讀(1326) |
評論 (0) |
編輯 收藏
題目大意：
去掉給定的邊，看每一個點是否能從別的點到達！
如果能夠到達，則求出對于每一個點到其他所有的點最短距離之和，將這些和相加就是最后的結果
解題思路：
對每一個點求一次單源最短路，然后求和，相加的到最后的結果……
但，算一下時間復雜度： 復雜度是O(M*N*M)。由于M*N*M=3000*100*3000=9*10
8，不可能AC
所以，需要我們另辟他徑。網上有說建什么最短路徑樹，這個我不懂……
我的思路是：引用前面的思路，對每一個點求一次最短路，并將其求和，保存在一個數組里頭，定為sum[i]，i表示著一個點到所有其他點最短路之和。并將這些和相加 ans = sum[1] + …… + sum[n];
然后，刪除一條邊，其頂點暫定為u,v，對這條邊的一個頂點u在一次求最短路，如果這個點，不能到達這條邊的另一個點v，則 直接輸出INF
如果，能夠到達，則對v也求一次最短路，對于u，v兩點來說，求得u到每一個點的最短路之和sum_u，求得v到每一個點的最短路之和sum_v，
最后結果為： ans = ans + sum_u + sum_v - sum[u] - sum[v];
ans為最后答案（千萬記住是每一組的，因為有m條邊）
具體看代碼：
http://acm.hdu.edu.cn/showproblem.php?pid=2433時間是 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 路修遠 閱讀(1923) |
評論 (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算法！
其實這個題求的是最小權匹配，，但有些題目最小不一定好求，于是我們可以換一種思維，將有所的距離變成負的，那么我們要求的就是最大權匹配！（在一位大牛的指點下）
廢話不多說，看程序：
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 路修遠 閱讀(1453) |
評論 (0) |
編輯 收藏
沒什么好說的，直接匈牙利算法
#include<iostream>
using namespace std;
int n,m;//n為x集合，m為y集合
int map[305][305];//map[x][y]表示x,y兩點之間有邊相連
bool visit[305];//記錄m中的i節點是否被訪問過
int link[305];//記錄當前n中的i節點是否與 j節點相連
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;//最大匹配數
}
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 路修遠 閱讀(1272) |
評論 (0) |
編輯 收藏
其實這個題，和我上次講的那個連連看一樣！只不過是字符變成了整型而已！
還是貼一下關鍵代碼吧(⊙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 //對game[x1][y1]四個方向是空格的標為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 //對gk[i][j]為1的四個方向是空格的標為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 //對gk[i][j]為2的四個方向是空格的標為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 路修遠 閱讀(1829) |
評論 (0) |
編輯 收藏
其實這個題是一個簡單的搜索問題，理解了很好做！注意4代表時間復原就行了！具體的在程序里頭，這里就不多說了，深知多說無益，還是要多練的！
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 //數組的交換
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時，p應該是0以上，
22 //剛開始是沒搞清楚，p大于0,wa了幾次，就是沒找到錯誤！
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 //輸出路徑，偏于查找當前的坐標位置和剩余時間p
41 fun(tt,tp);
42 memset(tp,0,sizeof(tp));
43 //到4是可以往回搜的，所以前面的走過的路徑應該移除標記
44 //用數組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 //輸出路徑，偏于查找當前的坐標位置和剩余時間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 路修遠 閱讀(1513) |
評論 (0) |
編輯 收藏
“九宮填數“也叫“九方數”，古代稱為“九宮算”。九宮填數是將九個有效數字填在九個方位格子里，要使每行、每列和每條對角線上的和都相等，即：橫的三個數之和、豎的三個數之和與斜的三個數之和，都相等。在解這個題之前，先把九宮的方位問題明確了，以便講行具體的闡述。
這個方位的確定與看地圖的方位是一致的。由于要把1—9這九個數填在適當的格子里，這九個數之和是45，無論是橫、豎、斜都是三個數，把45平均分成三行，每行三個數的和都是15（包括橫、豎、斜）。每三個數的情況：橫有3種，豎有3種，斜有2種，共8種。
只要知道三個數就可以枚舉所有的數了；
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 路修遠 閱讀(507) |
評論 (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.
以為要數組，想想，不是那么回事！
挺簡單的~~
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 路修遠 閱讀(479) |
評論 (0) |
編輯 收藏