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 阅读(1649) 评论(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   博问   Chat2DB   管理