{"id":13,"date":"2022-06-04T10:52:00","date_gmt":"2022-06-04T02:52:00","guid":{"rendered":"http:\/\/ubuntu.tim-wcx.ltd\/wordpress\/index.php\/2022\/06\/04\/2020-09-26-%e6%9c%80%e5%b0%8f%e8%b4%b9%e7%94%a8%e6%9c%80%e5%a4%a7%e6%b5%81%e9%97%ae%e9%a2%98\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-09-26-%e6%9c%80%e5%b0%8f%e8%b4%b9%e7%94%a8%e6%9c%80%e5%a4%a7%e6%b5%81%e9%97%ae%e9%a2%98","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-09-26-%e6%9c%80%e5%b0%8f%e8%b4%b9%e7%94%a8%e6%9c%80%e5%a4%a7%e6%b5%81%e9%97%ae%e9%a2%98\/","title":{"rendered":"2020-09-26 \u6700\u5c0f\u8d39\u7528\u6700\u5927\u6d41\u95ee\u9898"},"content":{"rendered":"

\n <\/path>\n <\/svg><\/p>\n

http:\/\/icpc.upc.edu.cn\/problem.php?cid=2587&pid=6<\/a><\/p>\n

<\/a>\u9898\u76ee\u63cf\u8ff0<\/h5>\n

Bonnie and Clyde have noticed that parallel processing improves throughput so, instead of robbing one bank together, they\u2019ve decided to rob two different banks simultaneously (each robbing one).
They both succeeded and now they need to run to their get-away 1934 Ford Model (730 Deluxe Sedan). There are complications, of course, or the movie won\u2019t be exciting!<\/p>\n

The city is in the shape of a matrix with cells. Bonnie and Clyde are in two different cells, and the get-away car is in a different cell as well. Bonnie and Clyde can move in four directions: north, south, east, and west (the border cells of course have fewer move options since they cannot move across the outer walls of the city). Some cells are also blocked, i.e., neither one can move into it.
To put more adventure in the movie, it is also the case that once Bonnie or Clyde moves into a cell, then neither one can move into that cell anymore, i.e., a cell is used at most once. Bonnie and Clyde cannot move into each other\u2019s starting position either.<\/p>\n

Given the city map (in the form of a matrix), the location for Bonnie, Clyde, and car, you are to compute the minimum total number of moves needed for both Bonnie and Clyde to get to the car, i.e., the total number of moves made by Bonnie plus the total number of moves made by Clyde.<\/p>\n

<\/a>\u8f93\u5165<\/h5>\n

The first input line contains two integers, r and c (2 \u2264 r, c \u2264 30), providing the number of rows and columns for the matrix. Each of the next r lines contains c characters, starting in column 1; this is the input matrix. There will be exactly one \u201cB\u201d (Bonnie\u2019s starting location), one \u201cC\u201d (Clyde\u2019s starting location), and one \u201cF\u201d (where the get-away Ford car is) in the input maze. The remaining cells will be \u201c.\u201d (empty cell \u2013 one can move into) or \u201cx\u201d (blocked \u2013 one cannot move into).<\/p>\n

<\/a>\u8f93\u51fa<\/h5>\n

Print the minimum total number of moves needed for both Bonnie and Clyde to get to the car. If they cannot get to the car, print -1. Note that when one reaches the car, he\/she stops moving.<\/p>\n

<\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n
6 5 \n..... \n...C. \n.B.x. \n..... \n...F. \n.....\n<\/code><\/pre>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n
9\n<\/code><\/pre>\n
<\/a>\u63d0\u793a<\/h5>\n
Bonnie can reach the car with 4 moves and Clyde can reach the car with 5 moves, for a total of 9 moves.<\/p>\n
#pragma<\/span> GCC optimize(1)<\/span>\n#pragma<\/span> GCC optimize(2)<\/span>\n#pragma<\/span> GCC optimize(3,\"Ofast\",\"inline\")<\/span>\n#include<\/span><\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\nstruct<\/span> node\n{<\/span>\n    int<\/span> next;<\/span>\n    int<\/span> flow;<\/span>\n    int<\/span> dis;<\/span>\n    int<\/span> to;<\/span>\n}<\/span>;<\/span>\nint<\/span> head[<\/span>100500<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\nnode edge[<\/span>100500<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> dis[<\/span>100500<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> pre[<\/span>100500<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> vis[<\/span>100500<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> last[<\/span>100500<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> flow[<\/span>100500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nchar<\/span> g[<\/span>1000<\/span>]<\/span>[<\/span>1000<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> n,<\/span>m,<\/span>s,<\/span>t,<\/span>cnt=<\/span>-<\/span>1<\/span>,<\/span>maxflow=<\/span>0<\/span>,<\/span>mincost=<\/span>0<\/span>;<\/span>\nint<\/span> num<\/span>(<\/span>int<\/span> i,<\/span>int<\/span> j)<\/span>\n{<\/span>\n    return<\/span> i*<\/span>m+<\/span>j;<\/span>\n}<\/span>\nint<\/span> add<\/span>(<\/span>int<\/span> from,<\/span>int<\/span> to,<\/span>int<\/span> flow,<\/span>int<\/span> dis)<\/span>\n{<\/span>\n    edge[<\/span>++<\/span>cnt]<\/span>.<\/span>next=<\/span>head[<\/span>from]<\/span>;<\/span>\n    edge[<\/span>cnt]<\/span>.<\/span>to=<\/span>to;<\/span>\n    edge[<\/span>cnt]<\/span>.<\/span>flow=<\/span>flow;<\/span>\n    edge[<\/span>cnt]<\/span>.<\/span>dis=<\/span>dis;<\/span>\n    head[<\/span>from]<\/span>=<\/span>cnt;<\/span>\n}<\/span>\nqueue<<\/span>int<\/span>><\/span>w;<\/span>\nbool<\/span> spfa<\/span>(<\/span>int<\/span> start,<\/span>int<\/span> end1)<\/span>\n{<\/span>\n    w.<\/span>push<\/span>(<\/span>start)<\/span>;<\/span>\n    memset<\/span>(<\/span>dis,<\/span>0x3f3f3f<\/span>,<\/span>sizeof<\/span>(<\/span>dis)<\/span>)<\/span>;<\/span>\n    memset<\/span>(<\/span>vis,<\/span>0<\/span>,<\/span>sizeof<\/span>(<\/span>vis)<\/span>)<\/span>;<\/span>\n    memset<\/span>(<\/span>flow,<\/span>0x3f3f3f<\/span>,<\/span>sizeof<\/span>(<\/span>flow)<\/span>)<\/span>;<\/span>\n    pre[<\/span>end1]<\/span>=<\/span>-<\/span>1<\/span>;<\/span>\n    vis[<\/span>start]<\/span>=<\/span>1<\/span>;<\/span>\n    dis[<\/span>start]<\/span>=<\/span>0<\/span>;<\/span>\n    while<\/span>(<\/span>!<\/span>w.<\/span>empty<\/span>(<\/span>)<\/span>)<\/span>\n    {<\/span>\n        int<\/span> now=<\/span>w.<\/span>front<\/span>(<\/span>)<\/span>;<\/span>\n        w.<\/span>pop<\/span>(<\/span>)<\/span>;<\/span>\n        vis[<\/span>now]<\/span>=<\/span>0<\/span>;<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>head[<\/span>now]<\/span>;<\/span> i!=<\/span>-<\/span>1<\/span>;<\/span> i=<\/span>edge[<\/span>i]<\/span>.<\/span>next)<\/span>\n        {<\/span>\n            \/\/cout<\n            if<\/span>(<\/span>edge[<\/span>i]<\/span>.<\/span>flow><\/span>0<\/span>&&<\/span>dis[<\/span>edge[<\/span>i]<\/span>.<\/span>to]<\/span>><\/span>dis[<\/span>now]<\/span>+<\/span>edge[<\/span>i]<\/span>.<\/span>dis)<\/span>\n            {<\/span>\n                dis[<\/span>edge[<\/span>i]<\/span>.<\/span>to]<\/span>=<\/span>dis[<\/span>now]<\/span>+<\/span>edge[<\/span>i]<\/span>.<\/span>dis;<\/span>\n                pre[<\/span>edge[<\/span>i]<\/span>.<\/span>to]<\/span>=<\/span>now;<\/span>\n                last[<\/span>edge[<\/span>i]<\/span>.<\/span>to]<\/span>=<\/span>i;<\/span>\n                flow[<\/span>edge[<\/span>i]<\/span>.<\/span>to]<\/span>=<\/span>min<\/span>(<\/span>flow[<\/span>now]<\/span>,<\/span>edge[<\/span>i]<\/span>.<\/span>flow)<\/span>;<\/span>\n                if<\/span>(<\/span>!<\/span>vis[<\/span>edge[<\/span>i]<\/span>.<\/span>to]<\/span>)<\/span>\n                {<\/span>\n                    vis[<\/span>edge[<\/span>i]<\/span>.<\/span>to]<\/span>=<\/span>1<\/span>;<\/span>\n                    w.<\/span>push<\/span>(<\/span>edge[<\/span>i]<\/span>.<\/span>to)<\/span>;<\/span>\n                }<\/span>\n            }<\/span>\n        }<\/span>\n    }<\/span>\n    return<\/span> pre[<\/span>end1]<\/span>!=<\/span>-<\/span>1<\/span>;<\/span>\n}<\/span>\nint<\/span> MCMF<\/span>(<\/span>)<\/span>\n{<\/span>\n    while<\/span>(<\/span>spfa<\/span>(<\/span>s,<\/span>t)<\/span>)<\/span>\n    {<\/span>\n        maxflow+<\/span>=<\/span>flow[<\/span>t]<\/span>;<\/span>\n        mincost+<\/span>=<\/span>dis[<\/span>t]<\/span>*<\/span>flow[<\/span>t]<\/span>;<\/span>\n        int<\/span> now=<\/span>t;<\/span>\n        while<\/span>(<\/span>now!=<\/span>s)<\/span>\n        {<\/span>\n            edge[<\/span>last[<\/span>now]<\/span>]<\/span>.<\/span>flow-<\/span>=<\/span>flow[<\/span>t]<\/span>;<\/span>\n            edge[<\/span>last[<\/span>now]<\/span>^<\/span>1<\/span>]<\/span>.<\/span>flow+<\/span>=<\/span>flow[<\/span>t]<\/span>;<\/span>\n            now=<\/span>pre[<\/span>now]<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    memset<\/span>(<\/span>head,<\/span>-<\/span>1<\/span>,<\/span>sizeof<\/span>(<\/span>head)<\/span>)<\/span>;<\/span>\n    scanf<\/span>(<\/span>\"%d%d\"<\/span>,<\/span>&<\/span>n,<\/span>&<\/span>m)<\/span>;<\/span>\n    s=<\/span>n*<\/span>m+<\/span>200<\/span>,<\/span>t=<\/span>n*<\/span>m+<\/span>100<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span> i<=<\/span>n;<\/span> i++<\/span>)<\/span>\n    {<\/span>\n        scanf<\/span>(<\/span>\"%s\"<\/span>,<\/span>g[<\/span>i]<\/span>+<\/span>1<\/span>)<\/span>;<\/span>\n    }<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span> i<=<\/span>n;<\/span> i++<\/span>)<\/span>\n    {<\/span>\n        for<\/span>(<\/span>int<\/span> j=<\/span>1<\/span>;<\/span> j<=<\/span>m;<\/span> j++<\/span>)<\/span>\n        {<\/span>\n            if<\/span>(<\/span>g[<\/span>i]<\/span>[<\/span>j]<\/span>==<\/span>'x'<\/span>)<\/span>\n                continue<\/span>;<\/span>\n            if<\/span>(<\/span>j><\/span>1<\/span>&&<\/span>g[<\/span>i]<\/span>[<\/span>j-<\/span>1<\/span>]<\/span>!=<\/span>'x'<\/span>)<\/span>\n            {<\/span>\n                add<\/span>(<\/span>num<\/span>(<\/span>i,<\/span>j)<\/span>,<\/span>num<\/span>(<\/span>i,<\/span>j-<\/span>1<\/span>)<\/span>,<\/span>1<\/span>,<\/span>1<\/span>)<\/span>;<\/span>\n                add<\/span>(<\/span>num<\/span>(<\/span>i,<\/span>j-<\/span>1<\/span>)<\/span>,<\/span>num<\/span>(<\/span>i,<\/span>j)<\/span>,<\/span>0<\/span>,<\/span>-<\/span>1<\/span>)<\/span>;<\/span>\n            }<\/span>\n            if<\/span>(<\/span>i><\/span>1<\/span>&&<\/span>g[<\/span>i-<\/span>1<\/span>]<\/span>[<\/span>j]<\/span>!=<\/span>'x'<\/span>)<\/span>\n            {<\/span>\n                add<\/span>(<\/span>num<\/span>(<\/span>i,<\/span>j)<\/span>,<\/span>num<\/span>(<\/span>i-<\/span>1<\/span>,<\/span>j)<\/span>,<\/span>1<\/span>,<\/span>1<\/span>)<\/span>;<\/span>\n                add<\/span>(<\/span>num<\/span>(<\/span>i-<\/span>1<\/span>,<\/span>j)<\/span>,<\/span>num<\/span>(<\/span>i,<\/span>j)<\/span>,<\/span>0<\/span>,<\/span>-<\/span>1<\/span>)<\/span>;<\/span>\n            }<\/span>\n            if<\/span>(<\/span>j<<\/span>m&&<\/span>g[<\/span>i]<\/span>[<\/span>j+<\/span>1<\/span>]<\/span>!=<\/span>'x'<\/span>)<\/span>\n            {<\/span>\n                add<\/span>(<\/span>num<\/span>(<\/span>i,<\/span>j)<\/span>,<\/span>num<\/span>(<\/span>i,<\/span>j+<\/span>1<\/span>)<\/span>,<\/span>1<\/span>,<\/span>1<\/span>)<\/span>;<\/span>\n                add<\/span>(<\/span>num<\/span>(<\/span>i,<\/span>j+<\/span>1<\/span>)<\/span>,<\/span>num<\/span>(<\/span>i,<\/span>j)<\/span>,<\/span>0<\/span>,<\/span>-<\/span>1<\/span>)<\/span>;<\/span>\n            }<\/span>\n            if<\/span>(<\/span>i<<\/span>n&&<\/span>g[<\/span>i+<\/span>1<\/span>]<\/span>[<\/span>j]<\/span>!=<\/span>'x'<\/span>)<\/span>\n            {<\/span>\n                add<\/span>(<\/span>num<\/span>(<\/span>i,<\/span>j)<\/span>,<\/span>num<\/span>(<\/span>i+<\/span>1<\/span>,<\/span>j)<\/span>,<\/span>1<\/span>,<\/span>1<\/span>)<\/span>;<\/span>\n                add<\/span>(<\/span>num<\/span>(<\/span>i+<\/span>1<\/span>,<\/span>j)<\/span>,<\/span>num<\/span>(<\/span>i,<\/span>j)<\/span>,<\/span>0<\/span>,<\/span>-<\/span>1<\/span>)<\/span>;<\/span>\n            }<\/span>\n            if<\/span>(<\/span>g[<\/span>i]<\/span>[<\/span>j]<\/span>==<\/span>'F'<\/span>)<\/span>\n            {<\/span>\n                add<\/span>(<\/span>s,<\/span>num<\/span>(<\/span>i,<\/span>j)<\/span>,<\/span>2<\/span>,<\/span>0<\/span>)<\/span>;<\/span>\n                add<\/span>(<\/span>num<\/span>(<\/span>i,<\/span>j)<\/span>,<\/span>s,<\/span>0<\/span>,<\/span>0<\/span>)<\/span>;<\/span>\n            }<\/span>\n            if<\/span>(<\/span>g[<\/span>i]<\/span>[<\/span>j]<\/span>==<\/span>'C'<\/span>||<\/span>g[<\/span>i]<\/span>[<\/span>j]<\/span>==<\/span>'B'<\/span>)<\/span>\n            {<\/span>\n                add<\/span>(<\/span>num<\/span>(<\/span>i,<\/span>j)<\/span>,<\/span>t,<\/span>1<\/span>,<\/span>0<\/span>)<\/span>;<\/span>\n                add<\/span>(<\/span>t,<\/span>num<\/span>(<\/span>i,<\/span>j)<\/span>,<\/span>0<\/span>,<\/span>0<\/span>)<\/span>;<\/span>\n            }<\/span>\n        }<\/span>\n    }<\/span>\n    MCMF<\/span>(<\/span>)<\/span>;<\/span>\n   \/\/ cout<\n    if<\/span>(<\/span>maxflow!=<\/span>2<\/span>)<\/span>\n        printf<\/span>(<\/span>\"-1n\"<\/span>)<\/span>;<\/span>\n    else<\/span>\n        printf<\/span>(<\/span>\"%dn\"<\/span>,<\/span>mincost)<\/span>;<\/span>\n}<\/span>\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
http:\/\/icpc.upc.edu.cn\/pr…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-13","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/13","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/comments?post=13"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/13\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=13"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=13"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=13"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}