<output id="qn6qe"></output>

    1. <output id="qn6qe"><tt id="qn6qe"></tt></output>
    2. <strike id="qn6qe"></strike>

      亚洲 日本 欧洲 欧美 视频,日韩中文字幕有码av,一本一道av中文字幕无码,国产线播放免费人成视频播放,人妻少妇偷人无码视频,日夜啪啪一区二区三区,国产尤物精品自在拍视频首页,久热这里只有精品12
      代碼改變世界

      AcWing_4318_最短路徑

      2022-03-27 02:00  幻霞  閱讀(37)  評論(0)    收藏  舉報

      鏈接:https://www.acwing.com/problem/content/submission/code_detail/12529624/

       

       

       這道題目一開始的思路想的太簡單,給出了一個路徑,將這個路徑看做唯一能走的地圖,然后判斷是否有相鄰或者相交,

      然而事實上測試樣例中含有像UDR這種東西能夠把標記法直接干碎的數據 (然而事實上是筆者把某一步想的太絕對了)。

      因此不能大意,干脆擺爛一下,用默認起點(101,101)讀入路徑后可算出終點(x,y),從終點dfs回起點,更新到達每一個位置的最小長度,然后判斷終點的長度即可。

       

      #include<bits/stdc++.h>
      using namespace std;
      int m[305][305]= {0};
      int ssize;
      void dfs(int x,int y,int len) {
          static int dx[4]= {-1,1,0,0},dy[4]= {0,0,-1,1};
          for(int i=0; i<4; i++) {
              int tx=x+dx[i],ty=y+dy[i];
              //先計算下一個路徑的值        
              if(m[tx][ty]==-1) m[tx][ty]=len+1;
          }
          for(int i=0; i<4; i++) {
              int tx=x+dx[i],ty=y+dy[i];
              //只有比原來的值小的最優路徑才會去覆蓋
              if(m[tx][ty]>=len+1) dfs(tx,ty,len+1);
          }
      }
      
      int main() {
          string s;
          cin>>s;
          int x=101,y=101;
          m[101][101]=-1;
          for(int i=0; i<s.size(); i++) {
              if(s[i]=='L') x--;
              else if(s[i]=='R') x++;
              else if(s[i]=='U') y++;
              else if(s[i]=='D') y--;
              m[x][y]=-1;
          }
          dfs(x,y,1);
          if(m[101][101]<s.size()) cout<<"NO";
          else cout<<"YES";
          return 0;
      }
      

        

      看到這想到很久以前寫的一些尋路算法,改天研究一下。

       

      主站蜘蛛池模板: 亚洲中文字幕无码一久久区| 日韩精品卡一卡二卡三卡四| 国产午夜福利不卡在线观看| 亚洲综合色区另类av| 中文字幕日韩精品无码内射| 少妇被粗大的猛烈进出| 亚洲一级特黄大片一级特黄| 国产精品亚欧美一区二区三区| 中文人妻熟妇乱又伦精品| av天堂久久精品影音先锋 | 日韩中文字幕亚洲精品| 午夜福利国产精品小视频| 3d无码纯肉动漫在线观看| 精品国偷自产在线视频99| 久久这里只精品国产2| 国产小受被做到哭咬床单GV| 狠狠人妻久久久久久综合蜜桃| 国产色一区二区三区四区| 美乳丰满人妻无码视频| 97久久精品无码一区二区天美| 九九热在线免费视频精品| 国产精品午夜精品福利| 尚义县| 亚洲国产精品男人的天堂| 亚洲av无码之国产精品网址蜜芽| 国产精品成人免费视频网站京东| 人妻系列中文字幕精品| 毛片av在线尤物一区二区 | 中文字幕少妇人妻精品| b站永久免费看片大全| 狠狠综合久久av一区二| 精品久久丝袜熟女一二三| 18禁亚洲一区二区三区| 午夜福利日本一区二区无码| 伊人春色激情综合激情网| 一区二区三区四区精品视频| 亚洲国产超清无码专区| 精品国产成人午夜福利| 国产成人av电影在线观看第一页| 亚洲AV无码一二区三区在线播放| 蜜芽久久人人超碰爱香蕉|