最短路径字符串

#include <iostream>
#include <vector>
#include <string>
#include <limits>
#include <algorithm>
using namespace std;
 
class Solution {
public:
    int GetMinPathStringLength(int m, int n, string strTableContent) {
        vector<vector<int>> graph;
        int minSize = numeric_limits<int>::max();
        int count = 0;
        vector<int> row;
        for (char& ch : strTableContent) {
            if (ch == '|') {
                row.push_back(count);
                count = 0;
            }
            else if (ch == '/') {
                row.push_back(count);
                count = 0;
                graph.push_back(row);
                row.clear();
            }
            else
                count++;
        }
        vector<vector<int>> dp(m ,vector<int>(n));
        dp[0][0] = graph[0][0];
        for (int i = 1; i < m; i++)
            dp[i][0] = graph[i][0] + dp[i - 1][0];
        for (int i = 1; i < n; i++)
            dp[0][i] = graph[0][i] + dp[0][i - 1];
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + graph[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};

#include <cstring>
class Solution {
public:
    /**
     * 返回最短路径组成的字符串的长度
     * @param m int整型 表格行数
     * @param n int整型 表格列数
     * @param strTableContent string字符串 表格字符串表示
     * @return int整型
     */
    int GetMinPathStringLength(int m, int n, string strTableContent) {
        // write code here

        vector<vector<string>> grid(m,vector<string> (n));
        vector<vector<int>> res(m,vector<int> (n));
        vector<vector<int>> dp(m,vector<int> (n));
        vector<string> temp;    //只是暂存字符串 没什么用
        vector<int> strLen;
        stringstream ss(strTableContent);
        string row;
        while(getline(ss,row,'/'))
        {
            stringstream pix(row);
            string col;
            int cnt = 0;
            while (getline(pix, col, '|'))
            {
                cnt++;
                temp.push_back(col);
                strLen.push_back(col.size());
            }
            if (cnt < n)
            {
                temp.push_back("");
                strLen.push_back(0);
            }
        }

        int pos = 0;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                res[i][j] = strLen[pos++];
            }
        }
        dp[0][0] = res[0][0];
        for(int i = 1; i < m; ++i)
        {
            dp[i][0] = res[i][0] + dp[i-1][0];
        }
        for(int i = 1; i < n; ++i)
        {
            dp[0][i] = res[0][i] + dp[0][i-1];
        }

        for(int i = 1; i < m; ++i)
        {
            for(int j = 1; j < n; ++j)
            {
                dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + res[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};

vector<vector<int>> res(m, vector<int>(n, 0));
        int a = 0, b = 0;
        int count = 0;
        for (int i = 0; i < strTableContent.size(); i++)
            if (strTableContent[i] == '|' || strTableContent[i] == '/')
            {
                res[a][b] = count;
                count = 0;
                b++;
                if (b == n)
                {
                    a++;
                    b = 0;
                }
            }
            else
                count++;
        for(int i = 1; i < n; i++)
        {
            res[0][i] += res[0][i-1];
        }
        for(int i = 1; i < m; i++)
        {
            res[i][0] += res[i-1][0];
        }
        for(int i = 1; i< m; i++)
            for(int j = 1; j < n; j++)
                res[i][j] += min(res[i-1][j], res[i][j-1]);
        return res[m-1][n-1];

	class Solution {



	public:



	    /**



	     * 返回最短路径组成的字符串的长度



	     * @param m int整型 表格行数



	     * @param n int整型 表格列数



	     * @param strTableContent string字符串 表格字符串表示



	     * @return int整型



	     */



	    const int inf=0x3f3f3f3f;



	    struct node{



	    int val,x,y;



	    node(){};



	    node(int val,int x,int y)



	    {



	        this->val=val;



	        this->x=x;



	        this->y=y;



	    }



	    bool operator <(const node &t)const{



	    return x>t.x;



	    }



	};



	    int GetMinPathStringLength(int m, int n, string str) {



	        // write code here



	        swap(n,m);



	       int dir[2][2]={1,0,0,1},mp[105][105],dis[105][105];



	        int l=str.length(),val=0,pos=0;



	        memset(dis,inf,sizeof dis);



	        for(int i=0;i<l;i++)



	        {



	            if(str[i]=='|'||str[i]=='/'){



	                mp[pos/m][pos%m]=val;



	                val=0;



	                pos++;



	            }



	            else val++;



	        }



	        priority_queue<node>q;



	        q.push(node(mp[0][0],0,0));



	        dis[0][0]=mp[0][0];



	        while(!q.empty()){



	            node now=q.top();



	            q.pop();



	            for(int i=0;i<2;i++)



	            {



	                int nx=now.x+dir[i][0];



	                int ny=now.y+dir[i][1];



	                if(nx>=n||ny>=m)continue;



	                if(dis[nx][ny]>now.val+mp[nx][ny]){



	                    dis[nx][ny]=now.val+mp[nx][ny];



	                    q.push(node(dis[nx][ny],nx,ny));



	                }



	            }



	        }



	         



	    return dis[n-1][m-1];



	    }



	};