worm

为什么我的眼里饱含泪水?因为我程序没写完!
随笔 - 5, 文章 - 2, 评论 - 10, 引用 - 0
数据加载中……

poj 3414解题报告(广搜题)

                郁闷那,写了七个小时,一直在调试错误了!fuck it! 这个与别的BFS题的主要不同是要记录正确顺序的路径,我用path[i][j] = {way,a,b}表示状态(i,j)是由状态(a,b)经过方式way(一共六种方式)来得到的;呵呵,郁闷啊!
               不过值得高兴地是提交一次成功,呵呵,希望对大家有所帮助!下面是代码,很乱,请大家凑合着看吧,现在是没心情优化了!!
  1//============================================================================
  2// Name        : poj.cpp
  3// Author      :
  4// Version     :
  5// Copyright   : Your copyright notice
  6// Description : BFS
  7//============================================================================
  8
  9#include <iostream>
 10#include <queue>
 11int A, B, C;
 12int j = 1;
 13int result[101][101= 0 };
 14using namespace std;
 15struct node {
 16    int a;
 17    int b;
 18}
;
 19struct node2 {
 20    int pre;
 21    int m;
 22    int n;
 23}
 path[101][101];
 24int p[1000];
 25int visited[101][101= 0 };
 26int BFS(node x) {
 27    queue<node> q;
 28    q.push(x);
 29    visited[x.a][x.b] = 1;
 30    result[x.a][x.b] = 0;
 31    path[x.a][x.b].pre = 0;
 32    path[0][0].m = path[0][0].n = 0;
 33    while (!q.empty()) {
 34        node temp = q.front();
 35        q.pop();
 36        if (temp.a == C)
 37            return temp.b;
 38        if (temp.b == C) {
 39            j = 2;
 40            return temp.a;
 41        }

 42        node y;
 43        y.a = A;
 44        y.b = temp.b;
 45        if (temp.a < A && !visited[A][temp.b]) {
 46            q.push(y);
 47            visited[A][temp.b] = 1;
 48            result[y.a][y.b] = result[temp.a][temp.b] + 1;
 49            path[y.a][y.b].pre = 1;
 50            path[y.a][y.b].m = temp.a;
 51            path[y.a][y.b].n = temp.b;
 52        }

 53        y.a = temp.a;
 54        y.b = B;
 55        if (temp.b < B && !visited[y.a][y.b]) {
 56            q.push(y);
 57            visited[temp.a][B] = 1;
 58            result[y.a][y.b] = result[temp.a][temp.b] + 1;
 59            path[y.a][y.b].pre = 2;
 60            path[y.a][y.b].m = temp.a;
 61            path[y.a][y.b].n = temp.b;
 62
 63        }

 64        y.a = 0;
 65        y.b = temp.b;
 66        if (temp.a != 0 && !visited[0][temp.b]) {
 67            q.push(y);
 68            visited[0][temp.b] = 1;
 69            result[y.a][y.b] = result[temp.a][temp.b] + 1;
 70            path[y.a][y.b].pre = 3;
 71            path[y.a][y.b].m = temp.a;
 72            path[y.a][y.b].n = temp.b;
 73
 74        }

 75
 76        y.a = temp.a;
 77        y.b = 0;
 78        if (temp.b != 0 && !visited[temp.a][0]) {
 79            q.push(y);
 80            visited[temp.a][0= 1;
 81            result[y.a][y.b] = result[temp.a][temp.b] + 1;
 82            path[y.a][y.b].pre = 4;
 83            path[y.a][y.b].m = temp.a;
 84            path[y.a][y.b].n = temp.b;
 85
 86        }

 87        y.a = temp.a + temp.b - B;
 88        y.b = B;
 89        if (temp.a + temp.b > B && !visited[temp.a + temp.b - B][B]) {
 90            q.push(y);
 91            visited[temp.a + temp.b - B][B] = 1;
 92            result[y.a][y.b] = result[temp.a][temp.b] + 1;
 93            path[y.a][y.b].pre = 5;
 94            path[y.a][y.b].m = temp.a;
 95            path[y.a][y.b].n = temp.b;
 96
 97        }

 98        y.a = 0;
 99        y.b = temp.a + temp.b;
100        if (temp.a + temp.b <= B && !visited[0][temp.a + temp.b]) {
101            q.push(y);
102            visited[0][temp.a + temp.b] = 1;
103            result[y.a][y.b] = result[temp.a][temp.b] + 1;
104            path[y.a][y.b].pre = 5;
105            path[y.a][y.b].m = temp.a;
106            path[y.a][y.b].n = temp.b;
107
108        }

109        y.a = A;
110        y.b = temp.a + temp.b - A;
111        if (temp.a + temp.b > A && !visited[A][temp.a + temp.b - A]) {
112            q.push(y);
113            visited[A][temp.a + temp.b - A] = 1;
114            result[y.a][y.b] = result[temp.a][temp.b] + 1;
115            path[y.a][y.b].pre = 6;
116            path[y.a][y.b].m = temp.a;
117            path[y.a][y.b].n = temp.b;
118        }

119        y.a = temp.a + temp.b;
120        y.b = 0;
121        if (temp.a + temp.b <= A && !visited[temp.a + temp.b][0]) {
122            q.push(y);
123            visited[temp.a + temp.b][0= 1;
124            result[y.a][y.b] = result[temp.a][temp.b] + 1;
125            path[y.a][y.b].pre = 6;
126            path[y.a][y.b].m = temp.a;
127            path[y.a][y.b].n = temp.b;
128
129        }

130    }

131    return -1;
132}

133int main() {
134    cin >> A >> B >> C;
135    int i = 1;
136    int ff;
137    node x;
138    x.a = 0;
139    x.b = 0;
140    int m = BFS(x);
141    if (m == -1{
142        cout << "impossible" << endl;
143        return 0;
144    }

145    if (j == 1{
146        ff = result[C][m];
147        cout << result[C][m] << endl;
148        int x = C;
149        int y = m;
150        while (path[x][y].pre != 0{
151            p[i++= path[x][y].pre;
152            int temp1 = x;
153            int temp2 = y;
154            x = path[temp1][temp2].m;
155            y = path[temp1][temp2].n;
156        }

157    }

158    if (j == 2{
159        ff = result[m][C];
160        cout << result[m][C] << endl;
161        int x = m;
162        int y = C;
163        while (path[x][y].pre != 0{
164            p[i++= path[x][y].pre;
165            int temp1 = x;
166            int temp2 = y;
167            x = path[temp1][temp2].m;
168            y = path[temp1][temp2].n;
169        }

170    }

171    for (int i = ff; i >= 1; i--{
172        switch (p[i]) {
173        case 1:
174            cout << "FILL(1)" << endl;
175            break;
176        case 2:
177            cout << "FILL(2)" << endl;
178            break;
179        case 3:
180            cout << "DROP(1)" << endl;
181            break;
182        case 4:
183            cout << "DROP(2)" << endl;
184            break;
185        case 5:
186            cout << "POUR(1,2)" << endl;
187            break;
188        case 6:
189            cout << "POUR(2,1)" << endl;
190            break;
191        }

192
193    }

194    return 0;
195}

196

posted on 2009-03-08 18:40 WORM 阅读(1622) 评论(5)  编辑 收藏 引用

评论

# re: poj 3414解题报告(广搜题)[未登录]  回复  更多评论   

垃圾
2009-03-08 18:59 | A

# re: poj 3414解题报告(广搜题)  回复  更多评论   

@A 我承认本人是菜鸟,你牛逼你来搜人家的解题报告干嘛啊??
2009-03-08 19:03 | WORM

# re: poj 3414解题报告(广搜题)[未登录]  回复  更多评论   

我不是搜,订阅到博客天天是解体报告。。
2009-03-08 19:55 | A

# re: poj 3414解题报告(广搜题)  回复  更多评论   

已阅 删之
2009-03-08 20:24 | cppexplore

# re: poj 3414解题报告(广搜题)  回复  更多评论   

那我写啥?@A
2009-03-08 20:56 | WORM

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理