网格图必经点+dfs——cf1214D

不念不忘少年蓝@ 2023-10-11 07:49 32阅读 0赞

先正着走一次把所有可行路径标记出来，然后倒着走两条路径，一条是能向下就向下的路径，另一条能向右就向右。

如果这两条路径相交，那么(1,1)-(n,m)路径上比有个必经点，把这个必经点封上，答案是1，如果没有必经点答案是2，如果(1,1)-(n,m)不连通，答案是0

直接用递归dfs会爆栈。所以要用栈来代替递归

#include<bits/stdc++.h>
    using namespace std;
    #define N 1000005
    char mp[N];
    int n,m;
    struct Node{
        int x,y;
        Node(){}
        Node(int x,int y):x(x),y(y){}
    };
    stack<Node>stk;
    int vis[N],path[N];
    int id(int i,int j){
        return (i-1)*m+j;
    }
     
    int main(){
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("\n%c",&mp[id(i,j)]);
        
        stk.push(Node(1,1));
        while(stk.size()){
            Node c=stk.top();stk.pop();
            int x=c.x,y=c.y;
            if(vis[id(x,y)])continue;
            vis[id(x,y)]=1;
            
            if(x+1<=n && y<=m && mp[id(x+1,y)]=='.')
                stk.push(Node(x+1,y));
            if(x<=n && y+1<=m && mp[id(x,y+1)]=='.')
                stk.push(Node(x,y+1));    
        }
        
        if(!vis[id(n,m)]){puts("0");return 0;}
        
        while(stk.size())stk.pop();
        stk.push(Node(n,m));
        while(stk.size()){
            Node c=stk.top();stk.pop();
            int x=c.x,y=c.y;
            path[id(x,y)]++;
            
            if(x-1>0 && y>0 && vis[id(x-1,y)])
                stk.push(Node(x-1,y));
            else if(x>0 && y-1>0 && vis[id(x,y-1)])
                stk.push(Node(x,y-1));
        }
        
        while(stk.size())stk.pop();
        stk.push(Node(n,m));
        while(stk.size()){
            Node c=stk.top();stk.pop();
            int x=c.x,y=c.y;
            path[id(x,y)]++;
            
            if(x>0 && y-1>0 && vis[id(x,y-1)])
                stk.push(Node(x,y-1));
            else if(x-1>0 && y>0 && vis[id(x-1,y)])
                stk.push(Node(x-1,y));
        }
        for(int i=1;i<=n;i++)
            for (int j=1;j<=m;j++){
                if(i==1 && j==1)continue;
                if(i==n && j==m)continue;
                if(path[id(i,j)]==2){
                    puts("1");
                    return 0;
                }
            }
        puts("2");
        
    }

转载于:https://www.cnblogs.com/zsben991126/p/11462338.html