20分 样例过了错哪里呢
  • 板块P3395 路障
  • 楼主psyche_xin
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/1/16 21:03
  • 上次更新2025/1/17 10:18:32
查看原帖
20分 样例过了错哪里呢
1588333
psyche_xin楼主2025/1/16 21:03
#include <iostream>
#include  <cmath>
#include <cstring>
#include <vector>
using namespace std;
int ans=0;
int a[4]= {0,0,1,-1};
int b[4]= {1,-1,0,0};
int c[1005][1005];

int T,n;
bool legal(int i,int j);
bool check(int t,int i,int j);
void  bfs(int t,int i,int j);
int main()
{
    cin>>T;
   for(int k=1;k<=T;k++)
       {

            int x,y;
            ans=0;
            cin>>n;
            memset(c,0,sizeof(c));
            for(int i=1; i<=n*2-2; i++)
                {
                    cin>>y>>x;
                    c[y][x]=(i+1);
                }

                bfs(0,1,1);
                if(ans)
                    cout<<"Yes"<<endl;
                else
                    cout<<"No"<<endl;

        }

}
bool legal(int i,int j)
{
    return(i>0&&i<=n&&j>0&&j<=n);
}
bool check(int t,int i,int j)
{
    if(c[i][j]==0)
        return true;
    if(c[i][j]==1)
        return false;
    if(c[i][j]>t)
        return true;
    return false;
}
void  bfs(int t,int i,int j)//t=0;
{
    if(i==n&&j==n)
        {
            ans++;
            return;
        }
    for(int p=0; p<4; p++)
        {
            if(legal(i+a[p],j+b[p])&&check(t+1,i+a[p],j+b[p]))
                {

                    c[i+a[p]][j+b[p]]=1;
                    bfs(t+1,i+a[p],j+b[p]);

                }
        }
}
2025/1/16 21:03
加载中...