LeetCodeContest181

第三题

广搜，深搜都可以。

struct Node
{
    int x;
    int y;
    Node(){}
    Node(int x,int y)
    {
        this->x = x;
        this->y = y;
    }
};

class Solution {
public:
    int vis[500][500];
    int dir[6][2][2]={{{0,-1},{0,1}},{{-1,0},{1,0}},{{0,-1},{1,0}},{{0,1},{1,0}},{{0,-1},{-1,0}},{{0,1},{-1,0}}};
    bool hasValidPath(vector>& grid) {
        queue q;
        q.push(Node(0,0));
        vis[0][0]=1;
        int n=grid.size();
        int m=grid[0].size();
        while(!q.empty())
        {
            Node term = q.front();
            q.pop();
            
            if(term.x==n-1&&term.y==m-1)
                return true;
            
            int x = grid[term.x][term.y];
            
            for(int i=0;i<2;i++)
            {
                int xx = term.x + dir[x-1][i][0];
                int yy = term.y + dir[x-1][i][1];
                
                if(xx<0||xx>=n||yy<0||yy>=m)
                    continue;
                if(vis[xx][yy]==1)
                    continue;
                
                if(!judge(x,i,grid[xx][yy]))
                    continue;
                
                vis[xx][yy]=1;
                q.push(Node(xx,yy));
            }
            
        }
        return false;
    }
    
    bool judge(int x,int z,int y)
    {
        if(x==1&&z==0&&(y==1||y==4||y==6))
            return true;
        if(x==1&&z==1&&(y==1||y==3||y==5))
            return true;
        if(x==2&&z==0&&(y==2||y==3||y==4))
            return true;
        if(x==2&&z==1&&(y==2||y==5||y==6))
            return true;
        if(x==3&&z==0&&(y==1||y==4||y==6))
            return true;
        if(x==3&&z==1&&(y==2||y==3||y==5))
            return true;
        
        if(x==4&&z==0&&(y==1||y==3||y==5))
            return true;
        if(x==4&&z==1&&(y==2||y==5||y==6))
            return true;
        
         if(x==5&&z==0&&(y==1||y==4||y==6))
            return true;
        if(x==5&&z==1&&(y==2||y==3||y==4))
            return true;
        
         if(x==6&&z==0&&(y==1||y==3||y==5))
            return true;
        if(x==6&&z==1&&(y==2||y==3||y==4))
            return true;
        return false;
    }
};

第四题

KMP 的求最长公共前后缀的部分，就是Next的部分

class Solution {
public:
    int next[100005];
    string longestPrefix(string s) {
        
        getNext(s);
        
        int len = next[s.length()-1];
        
        string ans="";
        for(int i=0;i