C++博客-路修远

hdu 2757 Ocean Currents

路修远 — Sun, 22 Apr 2012 12:23:00 GMT

      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

路修远 2012-04-22 20:23 发表评论

Hdoj 2364 Escape

路修远 — Fri, 13 Apr 2012 10:34:00 GMT

      单纯的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

路修远 2012-04-13 18:34 发表评论

HDU 2433 最短路

路修远 — Fri, 09 Mar 2012 07:35:00 GMT

题目大意：
   去掉给定的边，看每一个点是否能从别的点到达！
    如果能够到达，则求出对于每一个点到其他所有的点最短距离之和，将这些和相加就是最后的结果

   解题思路：
      对每一个点求一次单源最短路，然后求和，相加的到最后的结果……
      但，算一下时间复杂度：复杂度是O(M*N*M)。由于M*N*M=3000*100*3000=9*10⁸，不可能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

路修远 2012-03-09 15:35 发表评论

poj 2195 Going Home

路修远 — Tue, 19 Apr 2011 05:54:00 GMT

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

路修远 2011-04-19 13:54 发表评论

poj 3020

路修远 — Tue, 05 Apr 2011 02:46:00 GMT

摘要: 阅读全文

路修远 2011-04-05 10:46 发表评论

poj 1274

路修远 — Mon, 04 Apr 2011 01:50:00 GMT

没什么好说的，直接匈牙利算法

#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;
}

路修远 2011-04-04 09:50 发表评论

hdoj 1175 连连看

路修远 — Wed, 24 Nov 2010 08:07:00 GMT

其实这个题，和我上次讲的那个连连看一样！只不过是字符变成了整型而已！
还是贴一下关键代码吧(⊙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        }

路修远 2010-11-24 16:07 发表评论

hdoj 1072 Nightmare!

路修远 — Tue, 09 Nov 2010 08:59:00 GMT

其实这个题是一个简单的搜索问题，理解了很好做！注意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<
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<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<<"->"<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

路修远 2010-11-09 16:59 发表评论

九宫填数源代码c++

路修远 — Wed, 30 Jun 2010 00:14:00 GMT

“九宫填数“也叫“九方数”，古代称为“九宫算”。九宫填数是将九个有效数字填在九个方位格子里，要使每行、每列和每条对角线上的和都相等，即：横的三个数之和、竖的三个数之和与斜的三个数之和，都相等。在解这个题之前，先把九宫的方位问题明确了，以便讲行具体的阐述。

　　这个方位的确定与看地图的方位是一致的。由于要把1—9这九个数填在适当的格子里，这九个数之和是45，无论是横、竖、斜都是三个数，把45平均分成三行，每行三个数的和都是15（包括横、竖、斜）。每三个数的情况：横有3种，竖有3种，斜有2种，共8种。

只要知道三个数就可以枚举所有的数了；

I	J
	5

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

路修远 2010-06-30 08:14 发表评论

HDU 1211 RSA

路修远 — Sat, 26 Jun 2010 10:59:00 GMT

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) = m^e mod n

When you want to decrypt data, use this method :

M = D(c) = c^d 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     }

路修远 2010-06-26 18:59 发表评论