首页 > 代码库 > Fire Net HDU 1045
Fire Net HDU 1045
简单深搜,可以完全暴力,不会超时的。
#include<iostream> #include<cstring> #include<cmath> using namespace std; #define MAX(a,b) (a>b?a:b) char maze[10][10]; int n, maxn; void DFS(int step,int count); int cheak(int x, int y); int main() { int i; while(scanf("%d",&n), n) { maxn = 0; for(i = 0; i < n; i++) scanf("%s",maze[i]); DFS(0,0); printf("%d\n",maxn); } return 0; } void DFS(int step,int count) { int x, y; maxn = MAX(maxn,count); if(step == n*n) return ; x = step/n; y = step%n; if(maze[x][y] == ‘.‘ && cheak(x,y)) { maze[x][y] = ‘O‘; DFS(step+1,count+1); maze[x][y] = ‘.‘; } DFS(step + 1, count); } int cheak(int x, int y) { int i; for(i = x-1; i >= 0; i--) { if(maze[i][y] == ‘O‘) return 0; else if(maze[i][y] == ‘X‘) break; } for(i = y-1; i >= 0; i--) { if(maze[x][i] == ‘O‘) return 0; else if(maze[x][i] == ‘X‘) break; } return 1; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。