Snowman » 日志 » zoj 1002 Fire Net
zoj 1002 Fire Net
snowman 发表于 2008-12-27 16:16:35
原题：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=2
算法：回溯
#include <stdio.h>
int board[4][4], n, ans, count;
/*0 空地 1 墙 2碉堡
programed by snowman 2008.12.27
*/
int islegal(int x, int y)
{
int i;
if(board[x][y] == 1 || board[x][y] == 2) return 0;
i = x; i --;
while( i >= 0)
{
if(board[i][y] == 2) return 0;
else if(board[i][y] == 1) break;
i --;
}
i = x; i ++;
while( i < n)
{
if(board[i][y] == 2) return 0;
else if(board[i][y] == 1) break;
i ++;
}
i = y; i --;
while( i >= 0)
{
if(board[x][i] == 2) return 0;
else if(board[x][i] == 1) break;
i --;
}
i = y; i ++;
while( i < n)
{
if(board[x][i] == 2) return 0;
else if(board[x][i] == 1) break;
i ++;
}
return 1;
}
void dfs()
{
int i, j;
for( i = 0; i < n; i ++)
for(j = 0; j < n; j ++)
if(islegal(i, j))
{
board[i][j] = 2;
count ++;
dfs();
count --;
board[i][j] = 0;
}
if(count > ans) ans = count ;
}
int main()
{
char str[5];
int i, j;
while(scanf("%d", &n), n)
{
for(i = 0; i < n; i ++)
{
scanf("%s", str);
for(j = 0; j < n; j ++)
if(str[j] == '.') board[i][j] = 0;
else board[i][j] = 1;
}
ans = 0; count = 0;
dfs();
printf("%d\n", ans);
}
return 1;
}
算法：回溯
#include <stdio.h>
int board[4][4], n, ans, count;
/*0 空地 1 墙 2碉堡
programed by snowman 2008.12.27
*/
int islegal(int x, int y)
{
int i;
if(board[x][y] == 1 || board[x][y] == 2) return 0;
i = x; i --;
while( i >= 0)
{
if(board[i][y] == 2) return 0;
else if(board[i][y] == 1) break;
i --;
}
i = x; i ++;
while( i < n)
{
if(board[i][y] == 2) return 0;
else if(board[i][y] == 1) break;
i ++;
}
i = y; i --;
while( i >= 0)
{
if(board[x][i] == 2) return 0;
else if(board[x][i] == 1) break;
i --;
}
i = y; i ++;
while( i < n)
{
if(board[x][i] == 2) return 0;
else if(board[x][i] == 1) break;
i ++;
}
return 1;
}
void dfs()
{
int i, j;
for( i = 0; i < n; i ++)
for(j = 0; j < n; j ++)
if(islegal(i, j))
{
board[i][j] = 2;
count ++;
dfs();
count --;
board[i][j] = 0;
}
if(count > ans) ans = count ;
}
int main()
{
char str[5];
int i, j;
while(scanf("%d", &n), n)
{
for(i = 0; i < n; i ++)
{
scanf("%s", str);
for(j = 0; j < n; j ++)
if(str[j] == '.') board[i][j] = 0;
else board[i][j] = 1;
}
ans = 0; count = 0;
dfs();
printf("%d\n", ans);
}
return 1;
}
相关日志:
- » 七天七夜
- » ACM退役宣言
- » 不给力_Halo@杭州
- » 小遗憾_Halo@jakarta
- » 惊天逆转_Halo@成都
收藏:
QQ书签
del.icio.us
