fork download 
  1. using System.Text;
  2.  
  3. static class Program
  4. {
  5.     public static List<T> Resize<T>(this List<T> list, int n, T var)
  6.     {
  7.         int count = list.Count;
  8.  
  9.         if (n < count)
  10.         {
  11.             list.RemoveRange(n, count - n);
  12.         }
  13.         else if (n > count)
  14.         {
  15.             if (n > list.Capacity)   // Optimization
  16.                 list.Capacity = n;
  17.  
  18.             list.AddRange(Enumerable.Repeat(var, n - count));
  19.         }
  20.  
  21.         return list;
  22.     }
  23.     public static List<T> Resize<T>(this List<T> lt, int n)
  24.         => lt.Resize(n, default);
  25.     public static List<List<T>> Resize<T>(this List<List<T>> list, int n, int m, T var)
  26.     {
  27.         int count = list.Count;
  28.  
  29.         if (n < count)
  30.         {
  31.             list.RemoveRange(n, count - n);
  32.         }
  33.         else if (n > count)
  34.         {
  35.             for (int i = 0; i < n - count; i++)
  36.                 list.Add(new List<T>().Resize(m, var));
  37.         }
  38.  
  39.         return list;
  40.     }
  41.     public static List<List<T>> Resize<T>(this List<List<T>> lt, int n, int m)
  42.         => lt.Resize(n, m, default);
  43.  
  44.     struct Vector2
  45.     {
  46.         public int x, y;
  47.         public Vector2(int _x, int _y)
  48.         {
  49.             x = _x;
  50.             y = _y;
  51.         }
  52.     }
  53.     class Graph
  54.     {
  55.         public int n;
  56.         public List<List<int>> E;
  57.         public Graph(int _n)
  58.         {
  59.             n = _n;
  60.             E = new List<List<int>>();
  61.             E.Resize(n, 0);
  62.         }
  63.         public void add_edge(int u, int v, bool bi = false)
  64.         {
  65.             E[u].Add(v);
  66.             if (bi) E[v].Add(u);
  67.         }
  68.         public List<bool> BFS(int s)
  69.         {
  70.             Queue<int> q = new Queue<int>();
  71.             List<bool> vit = new List<bool>();
  72.             vit.Resize(n, false);
  73.             q.Enqueue(s); vit[s] = true;
  74.             while (q.Count > 0)
  75.             {
  76.                 int top = q.Dequeue();
  77.                 foreach (int t in E[top])
  78.                 {
  79.                     if (vit[t]) continue;
  80.                     vit[t] = true;
  81.                     q.Enqueue(t);
  82.                 }
  83.             }
  84.             return vit;
  85.         }
  86.     }
  87.     class SCC : Graph
  88.     {
  89.         public int sccCount;
  90.         public List<List<int>> scc;
  91.         public List<int> group;
  92.  
  93.         private Stack<int> stk;
  94.         private List<bool> fin;
  95.         private List<int> dfsn;
  96.  
  97.         private int cnt;
  98.  
  99.         public SCC(int _n) : base(_n)
  100.         {
  101.             cnt = 0;
  102.             fin = new List<bool>();
  103.             fin.Resize(n, false);
  104.  
  105.             scc = new List<List<int>>();
  106.             scc.Resize(n, 0);
  107.  
  108.             group = new List<int>();
  109.             group.Resize(n, -1);
  110.  
  111.             dfsn = new List<int>();
  112.             dfsn.Resize(n, 0);
  113.  
  114.             stk = new Stack<int>();
  115.         }
  116.         private int dfs(int u)
  117.         {
  118.             dfsn[u] = ++cnt;
  119.             stk.Push(u);
  120.  
  121.             int ret = dfsn[u];
  122.             foreach (int v in E[u])
  123.             {
  124.                 if (dfsn[v] == 0) ret = Math.Min(ret, dfs(v));
  125.                 else if (!fin[v]) ret = Math.Min(ret, dfsn[v]);
  126.             }
  127.             if (ret == dfsn[u])
  128.             {
  129.                 List<int> now = new List<int>();
  130.                 while (true)
  131.                 {
  132.                     int top = stk.Pop();
  133.                     now.Add(top);
  134.                     fin[top] = true;
  135.                     group[top] = sccCount;
  136.                     if (top == u) break;
  137.                 }
  138.                 scc.Add(now);
  139.                 sccCount++;
  140.             }
  141.             return ret;
  142.         }
  143.  
  144.         public void Create()
  145.         {
  146.             for (int i = 0; i < n; i++)
  147.                 if (dfsn[i] == 0) dfs(i);
  148.         }
  149.  
  150.         public Graph Compress()
  151.         {
  152.             int sz = sccCount;
  153.             Graph ans = new Graph(sz);
  154.             for (int i = 0; i < n; i++)
  155.             {
  156.                 foreach (int j in E[i])
  157.                 {
  158.                     int u = group[i], v = group[j];
  159.                     if (u != v) ans.add_edge(u, v);
  160.                 }
  161.             }
  162.             for (int i = 0; i < sz; i++)
  163.                 ans.E[i] = ans.E[i].Distinct().ToList();
  164.             return ans;
  165.         }
  166.     }
  167.     class TwoSat : SCC
  168.     {
  169.         public int size;
  170.         public TwoSat(int _n) : base(2 * _n)
  171.         {
  172.             size = _n;
  173.         }
  174.         private int inv(int x) { return x + size; }
  175.         public void add_clause(int u, int v, bool arev = false, bool brev = false)
  176.         {
  177.             int f1 = arev ? inv(u) : u, t1 = brev ? v : inv(v);
  178.             int f2 = brev ? inv(v) : v, t2 = arev ? u : inv(u);
  179.             add_edge(f1, t1);
  180.             add_edge(f2, t2);
  181.         }
  182.         public List<int> calc()
  183.         {
  184.             Create();
  185.  
  186.             bool ok = true;
  187.             for (int i = 0; i < size; i++)
  188.                 if (group[i] == group[inv(i)]) ok = false;
  189.             List<int> ans = new List<int>();
  190.             ans.Resize(size, -1);
  191.             if (ok)
  192.                 for (int i = 0; i < size; i++)
  193.                     ans[i] = Convert.ToInt32(group[i] > group[inv(i)]);
  194.             return ans;
  195.         }
  196.     }
  197.     class TiltMaze
  198.     {
  199.         public int n, m;
  200.         public List<string> arr;
  201.  
  202.         private int idx;
  203.         public TiltMaze(int _n, int _m)
  204.         {
  205.             n = _n; m = _m;
  206.             idx = 0;
  207.             arr = new List<string>();
  208.             arr.Resize(n, "");
  209.         }
  210.         public TiltMaze(int _n, int _m, List<string> _arr) : this(_n, _m)
  211.         {
  212.             ReadMap(_arr);
  213.         }
  214.  
  215.         private List<List<int>> num;
  216.         private List<Vector2> inum;
  217.         private List<Vector2> star = new List<Vector2>();
  218.         public void ReadMap(List<string> _arr)
  219.         {
  220.             num = new List<List<int>>();
  221.             num.Resize(n, m);
  222.  
  223.             inum = new List<Vector2>();
  224.             inum.Resize(n * m + 1, new Vector2(0, 0));
  225.  
  226.             arr = new List<string>(_arr);
  227.  
  228.             for (int i = 0; i < n; i++)
  229.                 for (int j = 0; j < m; j++)
  230.                 {
  231.                     if (arr[i][j] != '#')
  232.                     {
  233.                         num[i][j] = ++idx;
  234.                         inum[num[i][j]] = new Vector2(i, j);
  235.                     }
  236.                     if (arr[i][j] == 'O')
  237.                     {
  238.                         sx = i; sy = j;
  239.                     }
  240.                     else if (arr[i][j] == '*') star.Add(new Vector2(i, j));
  241.                 }
  242.         }
  243.  
  244.         private int sx, sy;
  245.  
  246.         private List<List<int>>[] dp;
  247.         private int[] dx = { 1, 0, -1, 0 };
  248.         private int[] dy = { 0, 1, 0, -1 };
  249.         private void FillDP()
  250.         {
  251.             dp = new List<List<int>>[4];
  252.             for (int i = 0; i < 4; i++)
  253.             {
  254.                 dp[i] = new List<List<int>>();
  255.                 dp[i].Resize(n, m);
  256.             }
  257.  
  258.             int tn = n, tm = m;
  259.             for (int k = 0; k < 4; k++)
  260.             {
  261.                 for (int i = 0; i < tm; i++)
  262.                 {
  263.                     int u = tn - 1, v = i;
  264.                     if (k > 1) u = 0;
  265.                     if (k % 2 == 1) (u, v) = (v, u);
  266.                     if (num[u][v] > 0) dp[k][u][v] = num[u][v];
  267.                 }
  268.                 List<int> lt = new List<int>();
  269.                 for (int i = 0; i < tn - 1; i++) lt.Add(i);
  270.                 if (k < 2) lt.Reverse();
  271.                 if (k > 1)
  272.                     for (int i = 0; i < lt.Count; i++) lt[i]++;
  273.                 foreach (int i in lt)
  274.                 {
  275.                     for (int j = 0; j < tm; j++)
  276.                     {
  277.                         int ni = i, nj = j;
  278.                         if (k % 2 == 1) (ni, nj) = (nj, ni);
  279.                         if (arr[ni][nj] != '#')
  280.                         {
  281.                             dp[k][ni][nj] = num[ni][nj];
  282.                             if (dp[k][ni + dx[k]][nj + dy[k]] > 0)
  283.                                 dp[k][ni][nj] = dp[k][ni + dx[k]][nj + dy[k]];
  284.                         }
  285.                     }
  286.                 }
  287.                 (tn, tm) = (tm, tn);
  288.             }
  289.         }
  290.  
  291.         private SCC scc;
  292.         private void ConstructSCC()
  293.         {
  294.             scc = new SCC(idx + 1);
  295.             for (int i = 0; i < n; i++)
  296.                 for (int j = 0; j < m; j++)
  297.                 {
  298.                     if (arr[i][j] == '#') continue;
  299.                     for (int k = 0; k < 4; k++)
  300.                         scc.add_edge(num[i][j], dp[k][i][j]);
  301.                 }
  302.             scc.Create();
  303.         }
  304.         private int GetSCCGroup(int g) => scc.group[g];
  305.         private int GetSCCGroup(int x, int y) => GetSCCGroup(num[x][y]);
  306.         public List<int> Calc()
  307.         {
  308.             FillDP();
  309.             ConstructSCC();
  310.  
  311.             int sz = scc.sccCount;
  312.             Graph compress = scc.Compress();
  313.  
  314.             int st = GetSCCGroup(sx, sy);
  315.  
  316.             TwoSat ts = new TwoSat(sz);
  317.             ts.add_clause(st, st);
  318.  
  319.             List<List<bool>> reach = new List<List<bool>>();
  320.             reach.Resize(sz, sz, false);
  321.  
  322.             for (int i = 0; i < sz; i++)
  323.                 reach[i] = new List<bool>(compress.BFS(i));
  324.  
  325.             for (int i = 0; i < sz; i++)
  326.             {
  327.                 if (!reach[st][i]) ts.add_clause(i, i, true, true);
  328.                 else
  329.                 {
  330.                     for (int j = 0; j < sz; j++)
  331.                     {
  332.                         if (!reach[st][j]) continue;
  333.                         if (!reach[i][j] && !reach[j][i]) ts.add_clause(i, j, true, true);
  334.                     }
  335.                 }
  336.             }
  337.  
  338.             foreach (Vector2 vec in star)
  339.             {
  340.                 int u = dp[0][vec.x][vec.y], v = dp[1][vec.x][vec.y];
  341.                 ts.add_clause(GetSCCGroup(u), GetSCCGroup(v));
  342.             }
  343.  
  344.             return ts.calc();
  345.         }
  346.  
  347.         private char Dir(Vector2 from, Vector2 to)
  348.         {
  349.             List<char> txt = new List<char>() { 'U', 'R', 'D', 'L' };
  350.             int nx = from.x - to.x, ny = from.y - to.y;
  351.             int tx = (nx == 0 ? 0 : nx / Math.Abs(nx)), ty = (ny == 0 ? 0 : ny / Math.Abs(ny));
  352.  
  353.             for (int j = 0; j < 4; j++)
  354.                 if (tx == dx[j] && ty == dy[j])
  355.                     return txt[j];
  356.             return ' ';
  357.         }
  358.         private string Routing(List<Vector2> poses)
  359.         {
  360.             List<char> txt = new List<char>() { 'U', 'R', 'D', 'L' };
  361.             string ans = "";
  362.             int n = poses.Count;
  363.             for (int i = 1; i < n; i++)
  364.                 ans.Append(Dir(poses[i - 1], poses[i]));
  365.             return ans;
  366.         }
  367.         public string Tracking(List<int> ret)
  368.         {
  369.             int sz = ret.Count;
  370.  
  371.             List<int> candidate = new List<int>();
  372.             List<bool> chk = new List<bool>();
  373.             chk.Resize(sz, false);
  374.             foreach (int i in ret)
  375.             {
  376.                 if (ret[i] == 1)
  377.                 {
  378.                     candidate.Add(i);
  379.                     chk[i] = true;
  380.                 }
  381.             }
  382.  
  383.             Graph compress = scc.Compress();
  384.  
  385.             List<int> ind = new List<int>();
  386.             ind.Resize(sz, 0);
  387.             for (int i = 0; i < sz; i++)
  388.             {
  389.                 if (!chk[i]) continue;
  390.                 foreach (int j in compress.E[i])
  391.                     if (chk[j]) ind[j]++;
  392.             }
  393.  
  394.             List<bool> start = new List<bool>(),
  395.                 end = new List<bool>(),
  396.                 vit = new List<bool>();
  397.             start.Resize(n, false);
  398.             end.Resize(n, false);
  399.             vit.Resize(n, false);
  400.  
  401.             Queue<int> q = new Queue<int>();
  402.             q.Enqueue(scc.group[num[sx][sy]]);
  403.  
  404.             List<int> ord = new List<int>();
  405.             while (q.Count > 0)
  406.             {
  407.                 int top = q.Dequeue();
  408.                 ord.Add(top);
  409.                 foreach (int j in compress.E[top])
  410.                 {
  411.                     if (!chk[j]) continue;
  412.                     if (--ind[j] == 0) q.Enqueue(j);
  413.                 }
  414.  
  415.                 Queue<int> que = new Queue<int>();
  416.                 foreach (int i in scc.scc[top])
  417.                 {
  418.                     if (i == num[sx][sy]) start[i] = true;
  419.                     if (start[i]) que.Enqueue(i);
  420.                 }
  421.  
  422.                 while (que.Count > 0)
  423.                 {
  424.                     int u = que.Dequeue();
  425.                     foreach (int v in scc.E[u])
  426.                     {
  427.                         if (vit[v]) continue;
  428.                         if (scc.group[u] == scc.group[v])
  429.                         {
  430.                             vit[v] = true;
  431.                             que.Enqueue(v);
  432.                         }
  433.                         else if (chk[scc.group[v]])
  434.                             start[v] = end[u] = true;
  435.                     }
  436.                 }
  437.             }
  438.  
  439.             List<int> lv = new List<int>();
  440.             lv.Resize(sz, 0);
  441.             for (int i = 0; i < ord.Count; i++)
  442.                 lv[ord[i]] = i;
  443.  
  444.             foreach (int i in scc.scc[ord[ord.Count - 1]])
  445.                 end[i] = true;
  446.  
  447.             Dictionary<Vector2, int> dis = new Dictionary<Vector2, int>();
  448.             Dictionary<Vector2, string> path = new Dictionary<Vector2, string>();
  449.  
  450.             foreach (int i in candidate)
  451.             {
  452.                 void ShortestPath(int g)
  453.                 {
  454.                     Dictionary<int, int> id = new Dictionary<int, int>();
  455.                     {
  456.                         int i = 0;
  457.                         foreach (int u in scc.scc[g]) id[u] = i++;
  458.                     }
  459.                     Dictionary<Vector2, int> road = new Dictionary<Vector2, int>();
  460.                     int scnt = 0, n = scc.scc[g].Count;
  461.  
  462.                     foreach (Vector2 vec in star)
  463.                     {
  464.                         List<Vector2> lt = new List<Vector2>();
  465.                         if (chk[scc.group[dp[0][vec.x][vec.y]]])
  466.                             lt.Add(new Vector2(dp[0][vec.x][vec.y], dp[2][vec.x][vec.y]));
  467.                         if (chk[scc.group[dp[1][vec.x][vec.y]]])
  468.                             lt.Add(new Vector2(dp[1][vec.x][vec.y], dp[3][vec.x][vec.y]));
  469.  
  470.                         if (lt.Count == 2)
  471.                         {
  472.                             if (lv[scc.group[lt[0].x]] > lv[scc.group[lt[1].x]])
  473.                                 (lt[0], lt[1]) = (lt[1], lt[0]);
  474.                         }
  475.                         if (scc.group[lt[0].x] == g)
  476.                         {
  477.                             road[lt[0]] = scnt;
  478.                             road[new Vector2(lt[0].y, lt[0].x)] = scnt;
  479.                             scnt++;
  480.                         }
  481.                     }
  482.  
  483.                     foreach (int s in scc.scc[g])
  484.                     {
  485.                         if (!start[s]) continue;
  486.                         List<List<int>> dst = new List<List<int>>();
  487.                         List<List<Vector2>> route = new List<List<Vector2>>();
  488.                         dst.Resize(n, 1<<scnt, -1);
  489.                         route.Resize(n, 1<<scnt,new Vector2(0, 0));
  490.  
  491.                         Queue<Vector2> q = new Queue<Vector2>();
  492.                         q.Enqueue(new Vector2(id[s], 0));
  493.                         dst[id[s]][0] = 0;
  494.                         while (q.Count > 0)
  495.                         {
  496.                             Vector2 top = q.Dequeue();
  497.                             int pos = top.x, state = top.y;
  498.                             foreach (int v in scc.E[pos])
  499.                             {
  500.                                 if (scc.group[v] != g) continue;
  501.                                 int tst = state;
  502.                                 Vector2 e = new Vector2(pos, id[v]);
  503.                                 if (road.ContainsKey(e)) tst |= (1 << road[e]);
  504.                                 if (dst[id[v]][tst] == -1)
  505.                                 {
  506.                                     dst[id[v]][tst] = dst[pos][state] + 1;
  507.                                     q.Enqueue(new Vector2(id[v], tst));
  508.                                     route[id[v]][tst] = top;
  509.                                 }
  510.                             }
  511.                         }
  512.  
  513.                         foreach (int e in scc.scc[g])
  514.                         {
  515.                             if (!end[e]) continue;
  516.                             dis[new Vector2(s, e)] = dst[id[e]][(1 << scnt) - 1];
  517.  
  518.                             List<Vector2> poses = new List<Vector2>();
  519.                             int now = e, nstate = (1 << scnt) - 1;
  520.                             while (true)
  521.                             {
  522.                                 if (now == s && nstate == 0) break;
  523.                                 Vector2 prv = route[now][nstate];
  524.                                 poses.Add(inum[now]);
  525.                                 now = prv.x; nstate = prv.y;
  526.                             }
  527.                             poses.Reverse();
  528.                             path[new Vector2(s, e)] = Routing(poses);
  529.                         }
  530.                     }
  531.                 }
  532.                 ShortestPath(i);
  533.             }
  534.  
  535.             List<List<int>>[] rdp = new List<List<int>>[2],
  536.                 id = new List<List<int>>[2],
  537.                 back = new List<List<int>>[2];
  538.  
  539.             for (int i = 0; i < 2; i++)
  540.             {
  541.                 rdp[i] = new List<List<int>>();
  542.                 rdp[i].Resize(ord.Count, 0);
  543.                 id[i] = new List<List<int>>();
  544.                 id[i].Resize(ord.Count, 0);
  545.                 back[i] = new List<List<int>>();
  546.                 back[i].Resize(ord.Count, 0);
  547.             }
  548.             for (int o = 0; o < ord.Count; o++)
  549.             {
  550.                 int st = 0, et = 0;
  551.                 foreach (int i in scc.scc[ord[o]])
  552.                 {
  553.                     if (start[i])
  554.                     {
  555.                         rdp[0][o].Add(0x3f3f3f3f);
  556.                         id[0][o].Add(i);
  557.                         back[0][o].Add(0);
  558.                     }
  559.                     if (end[i])
  560.                     {
  561.                         rdp[1][o].Add(0x3f3f3f3f);
  562.                         id[1][o].Add(i);
  563.                         back[1][o].Add(0);
  564.                     }
  565.                 }
  566.             }
  567.             rdp[0][0][0] = 0;
  568.             for (int o = 0; o < ord.Count; o++)
  569.             {
  570.                 int cnt = scc.scc[ord[o]].Count;
  571.                 if (o > 0)
  572.                 {
  573.                     for (int i = 0; i < cnt; i++)
  574.                     {
  575.                         if (!start[i]) continue;
  576.                         for (int j = 0; j < cnt; j++)
  577.                         {
  578.                             if (!end[j]) continue;
  579.                             int d = rdp[1][o - 1][j] + 1;
  580.                             if (rdp[0][o][i] > d)
  581.                             {
  582.                                 rdp[0][o][i] = d;
  583.                                 back[0][o][i] = j;
  584.                             }
  585.                         }
  586.                     }
  587.                 }
  588.                 for (int i = 0; i < cnt; i++)
  589.                 {
  590.                     if (!end[i]) continue;
  591.                     for (int j = 0; j < cnt; j++)
  592.                     {
  593.                         if (!start[j]) continue;
  594.                         int d = rdp[0][o][j] + dis[new Vector2(id[0][o][j], id[1][o][i])];
  595.                         if (rdp[1][o][i] > d)
  596.                         {
  597.                             rdp[1][o][i] = d;
  598.                             back[1][o][i] = j;
  599.                         }
  600.                     }
  601.                 }
  602.             }
  603.  
  604.             StringBuilder ans = new StringBuilder();
  605.             int now = 0;
  606.             for (int o = ord.Count - 1; o >= 0; o--)
  607.             {
  608.                 int e = id[1][o][now], t = back[1][o][now],
  609.                     s = id[0][o][t];
  610.                 string str = path[new Vector2(s, e)];
  611.                 str.Reverse();
  612.                 ans.Append(str);
  613.                 if (o > 0)
  614.                 {
  615.                     now = back[0][o][t];
  616.                     str.Append(Dir(inum[id[1][o - 1][now]], inum[s]));
  617.                 }
  618.  
  619.             }
  620.             for (int i = 0; i < ans.Length; i++)
  621.             {
  622.                 if (ans[i] == 'L') ans[i] = 'R';
  623.                 else if (ans[i] == 'R') ans[i] = 'L';
  624.                 else if (ans[i] == 'U') ans[i] = 'D';
  625.                 else if (ans[i] == 'D') ans[i] = 'U';
  626.             }
  627.             string temp = ans.ToString();
  628.             temp.Reverse();
  629.             return temp;
  630.         }
  631.     }
  632.  
  633.     static void Main(string[] args)
  634.     {
  635.         string[] txt = Console.ReadLine().Split(' ');
  636.         int n = int.Parse(txt[0]), m = int.Parse(txt[1]);
  637.         List<string> arr = new List<string>();
  638.         for (int i = 0; i < n; i++)
  639.             using (StringReader reader = new StringReader(Console.ReadLine()))
  640.                 arr.Add(reader.ReadLine());
  641.  
  642.         TiltMaze maze = new TiltMaze(n, m, arr);
  643.         List<int> ans = maze.Calc();
  644.  
  645.         if (ans[0] == -1) Console.WriteLine("NO");
  646.         else Console.WriteLine("YES");
  647.     }
  648. }
Runtime error #stdin #stdout #stderr 0.08s 29340KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
Unhandled exception. System.NullReferenceException: Object reference not set to an instance of an object.
   at Program.Main(String[] args) in /home/QDwuQW/Project/Program.cs:line 635
https://ideone.com/gmXcJf
language:
C# (NET 6.0)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!