Source code for submission s1140

ladybug.cpp

  1. #include <algorithm>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <complex>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <iomanip>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17. #include <vector>
  18.  
  19. using namespace std;
  20. #define DEBUG(x) cerr << ">>> " << #x << " : " << x << endl;
  21. #define REP(i,a) for (int i = 0; i < (a); ++i)
  22. #define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
  23. #define FORD(i,a,b) for (int i = (a); i >= (b); --i)
  24. inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
  25.  
  26. const int INF = 1<<29;
  27. typedef long long ll;
  28. //////////////////////////////////
  29.  
  30. int N;
  31. int dist[1001][1001][6][3];
  32.  
  33. /*
  34. OPERATOR:
  35. + 0
  36. - 1
  37. * 2
  38. / 3
  39. = 4
  40. N/A 5
  41. */
  42.  
  43. queue<int> qa, qb, qc, qd;
  44.  
  45. void add(int disp, int value, int  op, int state, int d){
  46.   if(disp < 1000 && disp >= 0 && dist[disp][value][op][state] == -1){
  47.     dist[disp][value][op][state] = d;
  48.     qa.push(disp);
  49.     qb.push(value);
  50.     qc.push(op);
  51.     qd.push(state);
  52.   }
  53. }
  54.  
  55. char oper[111];
  56. int OP;
  57.  
  58. int eval(int x, int y, int op){
  59.   if(op == 0) return x + y;
  60.   if(op == 1) return x - y;
  61.   if(op == 2) return x * y;
  62.   if(op == 3) return x / y;
  63. }
  64.  
  65. int decode(char c){
  66.   if(c == '+') return 0;
  67.   if(c == '-') return 1;
  68.   if(c == '*') return 2;
  69.   if(c == '/') return 3;
  70.   if(c == '=') return 4;
  71. }
  72.  
  73. int main() {
  74.   while(scanf("%s%d", oper, &N) != EOF){
  75.     OP = strlen(oper);
  76.     REP(i, 1000) REP(j, 1000) REP(k, 6) REP(l, 3) dist[i][j][k][l] = -1;
  77.     qa = queue<int>();
  78.     qb = queue<int>();
  79.     qc = queue<int>();
  80.     qd = queue<int>();
  81.     //while(!qa.empty()){ qa.pop(); qb.pop(); qc.pop(); qd.pop(); }
  82.     add(0, 0, 5, 2, 0);
  83.     bool ok = false;
  84.     while(!qa.empty()){
  85.       int disp = qa.front(), value = qb.front(), op = qc.front(), state = qd.front();
  86.       qa.pop(); qb.pop(); qc.pop(); qd.pop();
  87.       int d = dist[disp][value][op][state];
  88.       if(disp == N){ printf("%d\n", dist[disp][value][op][state]); ok = true; break; }
  89.       REP(i, OP){
  90.         char c = oper[i];
  91.         if(c <= '9' && c >= '0'){
  92.           int x = c - '0';
  93.           if(state == 0) add(x, value, op, 1, d+1); 
  94.           if(state == 1) add(10 * disp + x, value, op, 1, d+1);
  95.           if(state == 2) add(x, value, op, 1, d+1);
  96.         }
  97.         else{
  98.           int o = decode(c);
  99.           if(state == 1){
  100.             if(op < 3 || (op == 3 && disp)) add(eval(value, disp, op), eval(value, disp, op), o, 0, d+1);
  101.             if(op > 3) add(disp, disp, o, 0, d+1);
  102.           }
  103.           if(state == 0){
  104.             if(o == 4 && op != 4){ if(!(op == 3 && disp == 0)) add(eval(value, disp, op), eval(value, disp, op), o, 0, d+1); }
  105.             else add(disp, disp, o, 0, d+1);
  106.           }
  107.           if(state == 2) add(disp, value, o, 0, d+1);
  108.         }
  109.       }
  110.     }
  111.     if(!ok) printf("impossible\n");
  112.   }
  113.   return 0;
  114. }
  115.