2021 年百度之星·程序设计大赛

Problem Description

给定一张 n×nn×n 的网格图，有些格子能走，有些格子不能走，左上角的格子坐标为 (1,1)(1,1)，右下角的格子坐标为 (n,n)(n,n)。

问最多可以找到多少条从 (1,1)(1,1) 到 (n,n)(n,n) 的不相交路径，使得每条路径经过的每个格子（包含 (1,1)(1,1) 和 (n,n)(n,n)）都是能走的格子？

每次我们只可以向右或向下走，不能离开网格图的边界。两条路径不相交当且仅当除了格子 (1,1)(1,1) 和 (n,n)(n,n)，它们没有任何公共部分。

注意到答案要么是0，要么是1，要么是2（考虑起点一开始只能往两个格子走），简单dfs一下即可。注意特判起点终点为#的情况。

#include<bits/stdc++.h>

#define gcd(a,b) __gcd(a,b)
#define mod 1000000007
#define INF 0x3f3f3f3f3f
#define eps 1e-6    
#define pb push_back
#define rep(i,x,y) for(int i=x;i<y;i++)
#define mem(a,x) memset(a,x,sizeof(a))
#define IOS cin.tie(0), ios::sync_with_stdio(false)
#define maxn 100005
typedef long long ll; 
#define pll pair<ll,ll>
using namespace std;
bool vis[15][15];
char maze[15][15];
int ans,n;
bool check(int x, int y){
    if(x==n-1&&y==n-1) return true;
    if(x>=n||y>=n||vis[x][y]==true) return false;
    else return true;
}
bool dfs(int x, int y){
    if(ans==2) return true;
    if(x==n-1&&y==n-1){
        ans++;
        return true;
    }
    // cout<<"x"<<x<<"y"<<y<<endl;
    int nx=x+1;
    int ny=y;
    if(check(nx,ny)){
        vis[nx][ny]=true; 
        if(dfs(nx,ny)&&(x!=0||y!=0)) 
            return true;
    }
    nx=x;
    ny=y+1;
    if(check(nx,ny)){
        vis[nx][ny]=true; 
        if(dfs(nx,ny)&&(x!=0||y!=0)) 
            return true;
    }
    return false;
}
void solve(){
    cin>>n;
    rep(i,0,n){
        rep(j,0,n){
            cin>>maze[i][j];
            if(maze[i][j]=='#') vis[i][j]=true;
            else vis[i][j]=false;
        }
    }
    ans=0;
    if(maze[0][0]=='#'||maze[n-1][n-1]=='#') ans=0;
    else dfs(0,0);
    cout<<ans<<endl;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    } 
}

2021 年百度之星·程序设计大赛

相关推荐