1 条题解
-
0
C :
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<ctype.h> #include<math.h> int a[101][101],n,sx,sy,ex,ey,f;//f到达标志 void dfs(int i,int j){ a[i][j] = 1; if(i==ex && j==ey){ f = 1; return; } //不能超越格子,必须能通行,没有一条到终点 if(i-1>=1 && i-1<=n && a[i-1][j]==0 && f==0) dfs(i-1,j); if(i+1>=1 && i+1<=n && a[i+1][j]==0 && f==0) dfs(i+1,j); if(j-1>=1 && j-1<=n && a[i][j-1]==0 && f==0) dfs(i,j-1); if(j+1>=1 && j+1<=n && a[i][j+1]==0 && f==0) dfs(i,j+1); } int main(){ int i,j; scanf("%d",&n); for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ scanf("%d",&a[i][j]); } } scanf("%d%d%d%d",&sx,&sy,&ex,&ey); //递归深搜之前判断起点、终点是否有效 if(a[sx][sy]==1||a[ex][ey]==1) { printf("NO"); return 0; } //如果有效开始递归 dfs(sx,sy); //到底有没有到达终点 if(f==0) printf("NO"); else printf("YES"); return 0; }
C++ :
#include <iostream> using namespace std; int a[150][150],n,x1,y1,x2,y2; bool f = false;//表示有没有走到 //从x、y点开始逐步探测 void num(int x,int y){ if(x == x2 && y == y2){ f = true; }else{ a[x][y] = 1;//探测过的点,设置为不可探测,防止重复的探测 //上下左右探测,且不越界 if(x - 1 >= 1 && a[x - 1][y] == 0) num(x-1,y); if(x + 1 <= n && a[x + 1][y] == 0) num(x+1,y); if(y - 1 >= 1 && a[x][y - 1] == 0) num(x,y - 1); if(y + 1 <= n && a[x][y + 1] == 0) num(x,y + 1); } } int main(){ int i,j; cin>>n; //0表示能走,1表示不能走 for(i = 1;i <= n;i++){ for(j = 1;j <= n;j++){ cin>>a[i][j]; } } cin>>x1>>y1>>x2>>y2; //如果起止点有1,则不需要探测 if(a[x1][y1] == 1 || a[x2][y2] == 1){ cout<<"NO"<<endl; }else{ num(x1,y1); //探测完测试,如果走到了 if(f == true){ cout<<"YES"<<endl; }else{ cout<<"NO"<<endl; } } }
- 1
信息
- ID
- 2350
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者