[TIOJ 1442] 迷宮問題

一直把 n 和 m 搞反，多傳了好幾次才過QQ

作法：

最一般的作法就是把每格裡被切出的三角形都當成點，有相鄰的連邊，然後對他DFS或BFS，但看到記憶體限制可以知道如果把圖建出來會MLE，大概只開的下原本的圖而已。但注意到這張圖其實每個點的度頂多只有 2 ，並且在最上層的點的度只有1，所以以他為起點只有一條路徑，我們可以直接沿著這條路徑走，如果走的到最底下就把 ans ++ 。要注意到的是在走的過程中也可能會向上走。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=4000+5 ;
 
char G[maxn][maxn] ;
int n,m ;
 
int cal(int x)
{
    int x0=x ;
    for(int i=0,type=0;i<n;)
    {
        if(i<0) return 0 ;
        if(G[i][x]=='\\' && type==0)
        {
            if(x==m-1) return 0 ;
            if(G[i][x+1]=='/') x++ , i-- , type=1 ;
            else i++ , x++ ;
        }
        else if(G[i][x]=='\\' && type==1)
        {
            if(x==0) return 0 ;
            if(G[i][x-1]=='/') x-- , i++ , type=0 ;
            else i-- , x-- ;
        }
        else if(G[i][x]=='/' && type==0)
        {
            if(x==0) return 0 ;
            if(G[i][x-1]=='\\') x-- , i-- , type=1 ;
            else x-- , i++ ;
        }
        else
        {
            if(x==m-1) return 0 ;
            if(G[i][x+1]=='\\') x++ , i++ , type=0 ;
            else x++ , i-- ;
        }
    }
    return 1 ;
}
 
main()
{
    scanf("%d%d",&n,&m) ;
    swap(n,m) ;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
    {
        char c=getchar() ;
        while(c!='\\' && c!='/') c=getchar() ;
        G[i][j]=c ;
    }
    int ans=0 ;
    for(int i=0;i<m;i++) ans+=cal(i) ;
    if(ans) printf("%d\n",ans) ;
    else printf("I can't escape.\n") ;
}