2015年3月8日 星期日

[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") ;
}
 

1 則留言:

  1. If you want your ex-girlfriend or ex-boyfriend to come crawling back to you on their knees (no matter why you broke up) you need to watch this video
    right away...

    (VIDEO) Get your ex CRAWLING back to you...?

    回覆刪除