topcoder srm 628 div2 250 500

 1 #include <iostream>
 2 #include <cstring>
 3 #include <queue>
 4 #include <cmath>
 5 #include <cstdio>
 6 #include <algorithm>
 7 #include <vector>
 8 #define LL long long
 9 using namespace std;
10 
11 class BishopMove
12 {
13 public:
14     struct node
15     {
16         int x, y, step;
17     } next, pos;
18     int howManyMoves(int r1, int c1, int r2, int c2)
19     {
20         int vis[10][10], i, a, b;
21         memset(vis, 0, sizeof(vis));
22         if(r1==r2 && c1==c2)
23             return 0;
24 
25         queue<node>q;
26         vis[r1][c1] = 1;
27         next.x = r1;
28         next.y = c1;
29         next.step = 0;
30         q.push(next);
31         while(!q.empty())
32         {
33             pos = q.front();
34             if(pos.x == r2 && pos.y == c2)
35                 return pos.step;
36 
37             q.pop();
38             for(i = 1; i <= 7; i ++)
39             {
40                 a = pos.x+i;
41                 b = pos.y+i;
42                 if(a>=0&&a<=7 && b>=0 && b<=7 && vis[a][b]==0)
43                 {
44                     vis[a][b] = 1;
45                     next.x = a;
46                     next.y = b;
47                     next.step = pos.step+1;
48                     q.push(next);
49                 }
50                 a = pos.x+i;
51                 b = pos.y-i;
52                 if(a>=0&&a<=7 && b>=0 && b<=7 && vis[a][b]==0)
53                 {
54                     vis[a][b] = 1;
55                     next.x = a;
56                     next.y = b;
57                     next.step = pos.step+1;
58                     q.push(next);
59                 }
60                 a = pos.x-i;
61                 b = pos.y+i;
62                 if(a>=0&&a<=7 && b>=0 && b<=7 && vis[a][b]==0)
63                 {
64                     vis[a][b] = 1;
65                     next.x = a;
66                     next.y = b;
67                     next.step = pos.step+1;
68                     q.push(next);
69                 }
70                 a = pos.x-i;
71                 b = pos.y-i;
72                 if(a>=0&&a<=7 && b>=0 && b<=7 && vis[a][b]==0)
73                 {
74                     vis[a][b] = 1;
75                     next.x = a;
76                     next.y = b;
77                     next.step = pos.step+1;
78                     q.push(next);
79                 }
80             }
81         }
82         return -1;
83     }
84 };
85 
86 int main()
87 {
88     int r1, c1, r2, c2;
89     while(1)
90     {
91         cin>>r1>>c1>>r2>>c2;
92         BishopMove y;
93         cout<<y.howManyMoves(r1, c1, r2, c2)<<endl;
94     }
95     return 0;
96 }

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <cstdio>
 6 #include <vector>
 7 #define LL long long
 8 using namespace std;
 9 
10 class BracketExpressions
11 {
12 public:
13    int _max(int c, int d)
14    {
15        return c > d?c:d;
16    }
17    int match(char a, char b)
18    {
19        if(a==‘(‘ && b==‘)‘)
20        return 1;
21        if(a==‘{‘ && b==‘}‘)
22        return 1;
23        if(a==‘[‘ && b==‘]‘)
24        return 1;
25        if(a==‘X‘ &&(b==‘]‘||b==‘}‘||b==‘)‘))
26        return 1;
27        if(b==‘X‘ && (a==‘[‘||a==‘{‘||a==‘(‘))
28        return 1;
29        if(a==‘X‘ && b==‘X‘)
30        return 1;
31        return 0;
32    }
33    string ifPossible(string expression)
34    {
35        int i, j, k, g, len;
36        int d[100][100];
37        string s = expression;
38        len = s.size();
39        memset(d, 0, sizeof(d));
40        for(i = 0; i < len-1; i++)
41        if(match(s[i], s[i+1]))
42        d[i][i+1] = 1;
43        for(k = 2; k < len; k++)
44        {
45            for(i = 0; i < len-k; i++)
46            {
47                j = i+k;
48                if(match(s[i], s[j])) d[i][j] = d[i+1][j-1] + 1;
49                for(g = 0; g < k; g++)
50                d[i][j] = _max(d[i][i+g]+d[i+g+1][j], d[i][j]);
51            }
52        }
53        if(2*d[0][len-1]!=len)
54        return "impossible";
55        else
56        return "possible";
57    }
58 };