关于编程之美2014格格取数

  1 #include <iostream>
  2 #include <stack>
  3 #include <bitset>
  4 #include <set>
  5 
  6 using namespace std;
  7 int current_sum=0;
  8 int total_min = 0;//total_min是用来减枝，是全局最小的一个上限
  9 int row_number;
 10 int colomn_number;
 11 int** int_matrix;
 12 int* row_covered;
 13 int row_left;
 14 int colomn_left;
 15 long long  row_set[100];
 16 long long used_row_set[100];
 17 int temp_bitsum[100];
 18 int count_sum(long long  row_bit_set, int current_colomn_number)
 19 {
 20     int temp_sum = 0;
 21     int row_position = 0;
 22     while (row_bit_set)
 23     {
 24         temp_sum += (row_bit_set%2) * int_matrix[row_position++][current_colomn_number];
 25         row_bit_set=row_bit_set >> 1;
 26     }
 27     return temp_sum;
 28 }
 29 int all_covered()
 30 {
 31     for (int i = 0; i < row_number; i++)
 32     {
 33         if (row_covered[i] == 0)
 34         {
 35             return 0;
 36         }
 37     }
 38     return 1;
 39 }
 40 void dfs(int current_colomn)
 41 {
 42     long long temp_bitset = row_set[current_colomn];
 43     while (temp_bitset)
 44     {
 45         used_row_set[current_colomn] = temp_bitset;
 46         temp_bitsum[current_colomn] = count_sum(temp_bitset, current_colomn);
 47         if (current_sum + temp_bitsum[current_colomn] < total_min)//只有小于的时候才有必要进行下一次深度优先或者结束本次深度优先
 48         {
 49             current_sum = current_sum + temp_bitsum[current_colomn];
 50             for (int i = 0; i < row_number; i++)//对行进行mask
 51             {
 52                 row_covered[i] += temp_bitset%2;
 53                 temp_bitset=temp_bitset >> 1;
 54             }
 55             if (current_colomn == colomn_number-1)
 56             {
 57                 if (all_covered())//如果已经全部覆盖了，则表示这次深度优先搜索成功
 58                 {
 59                     total_min = current_sum ;//更新最小值
 60                 }
 61                 else//回溯，进行下一次试探
 62                 {
 63                     //什么都不需要干
 64                 }
 65                 //进行下一次试探
 66             }
 67             else
 68             {
 69                 
 70                 dfs(current_colomn + 1);//对下一列做dfs
 71             }
 72             temp_bitset = used_row_set[current_colomn];
 73             for (int i = 0; i < row_number; i++)//回溯 对行进行unmask
 74             {
 75                 row_covered[i] -= temp_bitset % 2;
 76                 temp_bitset=temp_bitset >> 1;
 77             }
 78             current_sum -= temp_bitsum[current_colomn];//回溯 将和往回降
 79         }
 80         temp_bitset = used_row_set[current_colomn];
 81         temp_bitset = (temp_bitset - 1)&row_set[current_colomn];
 82     }
 83 }
 84 int main()
 85 {
 86 
 87     cout << "please enter the row number" << endl;
 88     cin >> row_number;
 89     cout << "please enter the colomn number" << endl;
 90     //cin.get();//吃掉那一行，如果会换行的话
 91     cin >> colomn_number;
 92     cin.get();
 93     int_matrix = new int*[row_number];
 94     int_matrix[0] = new int[row_number*colomn_number];
 95     set<pair<int, int>> min_position;
 96     for (int i = 1; i < row_number; i++)
 97     {
 98         int_matrix[i] = int_matrix[i - 1] + colomn_number;
 99     }
100     for (int i = 0; i < row_number; i++)
101     {
102         for (int j = 0; j < colomn_number; j++)
103         {
104             cin >> int_matrix[i][j];
105         }
106     }
107     //下面记录行最小值和列最小值是为了减枝用
108     int* row_min = new int[row_number];
109     int* colomn_min = new int[colomn_number];
110     for (int i = 0; i < row_number; i++)//寻找行最小值
111     {
112         row_min[i] = 0;
113         for (int j = 1; j < colomn_number; j++)
114         {
115             if (int_matrix[i][row_min[i]]>int_matrix[i][j])
116             {
117                 row_min[i] = j;
118             }
119         }
120         min_position.insert(make_pair(i, row_min[i]));
121     }
122     for (int i = 0; i < colomn_number; i++)//寻找列最小值
123     {
124         colomn_min[i] = 0;
125         for (int j = 1; j < row_number; j++)
126         {
127             if (int_matrix[colomn_min[i]][j]>int_matrix[j][i])
128             {
129                 colomn_min[i] = j;
130             }
131         }
132         min_position.insert(make_pair(colomn_min[i], i));
133     }
134     for (auto temp_pair : min_position)
135     {
136         total_min += int_matrix[temp_pair.first][temp_pair.second];
137     }
138     for (int i = 0; i < colomn_number; i++)//初始化行的位数组
139     {
140         row_set[i] = (1 << row_number) - 1;
141     }
142     for (int i = 0; i < row_number; i++)
143     {
144         for (int j = 0; j < colomn_number; j++)
145         {
146             if (int_matrix[i][j]>int_matrix[i][row_min[i]] + int_matrix[colomn_min[j]][j])
147             {
148                 row_set[j]=row_set[j]&(~(1<<i));//标记为不可用
149             }
150         }
151     }
152     //准备开始深度优先搜索
153     row_covered = new int[row_number];
154     memset(row_covered, 0, sizeof(int) *row_number);
155     dfs(0);
156     cout << "current total min is " << total_min << endl;
157 }