What kind of algorithm can be used to solve this problem? http://poj.org/problem?id=3133 I suppose that dynamics and bit mask shall be adopted. I could not figure out how to express the accurate state of it. Thanks anyway
What kind of algorithm can be used to solve this problem? http://poj.org/problem?id=3133 I suppose that dynamics and bit mask shall be adopted. I could not figure out how to express the accurate state of it. Thanks anyway
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
I guess mincost flow is much easier for this problem than dp
Yes,we use DP with bitmask to solve this problem.We go through the map from top to bottom,and left to right.Let L be the border of cells we have visited and we haven't visited.So there is m+1 segment on L.One vertical segment,and m horizontal ones.State k contains 2*m+2 bits,because we need 2 bits to represent the state of a segment.
0:This segment isn't connected to a path.
1:This segment is connected with a "2" path.
2:This segment is connected with a "3" path.
dp[x][y][k] means the min length of the path after we visited cell (x,y) ,with the current state of L is k. Since there are so many states and lots of them are invaild,I used hash and queue. So the answer is dp[n][m][0].
Sorry,I'm not good at expressing,it is some kind of DP algorithm called "Plug DP" or "DP based on connectivity". If you you still have questions,just ask me or refer to my code here.