首页 > 代码库 > CF540C Ice Cave
CF540C Ice Cave
思路:
搜索。
加回溯会超时,不加回溯就过了,不是很理解。
实现:
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 5 const int dx[4] = { 0, 1, 0, -1 }, dy[4] = { 1, 0, -1, 0 }; 6 7 char a[505][505]; 8 int r, c, sx, sy, ex, ey; 9 10 bool dfs(int x, int y) 11 { 12 if (x == ex && y == ey && a[x][y] == ‘X‘) 13 { 14 return true; 15 } 16 a[x][y] = ‘X‘; 17 for (int i = 0; i < 4; i++) 18 { 19 int nx = x + dx[i]; 20 int ny = y + dy[i]; 21 if (nx >= 1 && nx <= r && ny >= 1 && ny <= c && 22 (a[nx][ny] == ‘.‘ || (nx == ex && ny == ey))) 23 { 24 if (dfs(nx, ny)) 25 return true; 26 } 27 } 28 return false; 29 } 30 31 int main() 32 { 33 cin >> r >> c; 34 for (int i = 1; i <= r; i++) 35 { 36 for (int j = 1; j <= c; j++) 37 { 38 cin >> a[i][j]; 39 } 40 } 41 cin >> sx >> sy >> ex >> ey; 42 a[sx][sy] = ‘.‘; 43 if (dfs(sx, sy)) 44 puts("YES"); 45 else 46 puts("NO"); 47 return 0; 48 }
CF540C Ice Cave
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。