Language:C++  Result:Wrong Answer

Source 

#include <stdio.h>

#define MAXN 5

int		fMap[MAXN][MAXN]; 
int		n, max; 

void changeState(int fi, int fj, int num, int revert)
{
	int i, j; 

	if (revert == 0) {
		fMap[fi][fj] = num; 
		for (i = fi, j = fj + 1; j < n  && fMap[i][j] != -1; j ++) 
			if (fMap[i][j] == 0) fMap[i][j] = num;
		for (i = fi, j = fj - 1; j >= 0 && fMap[i][j] != -1; j --) 
			if (fMap[i][j] == 0) fMap[i][j] = num;
		for (i = fi + 1, j = fj; i < n  && fMap[i][j] != -1; i ++) 
			if (fMap[i][j] == 0) fMap[i][j] = num;
		for (i = fi - 1, j = fj; i >= 0 && fMap[i][j] != -1; i --) 
			if (fMap[i][j] == 0) fMap[i][j] = num;
	} else {
		for (i = 0; i < n; i ++) 
			for (j = 0; j < n; j ++) 
				if (fMap[i][j] == num) fMap[i][j] = 0; 
	}
}

void DFS (int x, int y, int step, int tot)
{
	if (tot > max) max = tot; 
	if (x == n) return ; 
	if (y == n) { DFS(x + 1, 0, step, tot); return ;}
	if (fMap[x][y] == 0) {
		changeState(x, y, step, 0); 
		DFS(x, y + 1, step + 1, tot + 1);
		changeState(x, y, step, 1); 
	} else 
		DFS(x, y + 1, step, tot);
}

void main ()
{
	char	map[MAXN][MAXN]; 
	int		i, j, p, q; 

	while (1) {
		scanf("%d", &n); 
		if (n == 0) break; 
		for (i = 0; i < n; i ++) scanf("%s", map[i]); 
		max = 0; 
		for (i = 0; i < n; i ++) 
			for (j = 0; j < n; j ++) {
				for (p = 0; p < n; p ++)
					for (q = 0; q < n; q ++) 
						if (map[p][q] == '.') fMap[p][q] = 0;
						else fMap[p][q] = -1; 
				DFS(i, j, 1, 0); 				
			}
		printf("%d\n", max); 
	}
}

//////////////////////////////////

Language:C++  Result:Accepted

Source 

#include <stdio.h>

int n , max ;
int map[4][4];

void changeState(int fi, int fj, int num, int revert)
{
	int i, j; 

	if (revert == 0) {
		map[fi][fj] = num; 
		for (i = fi, j = fj + 1; j < n  && map[i][j] != 1; j ++) 
			if (map[i][j] == 0) map[i][j] = num;
		for (i = fi, j = fj - 1; j >= 0 && map[i][j] != 1; j --) 
			if (map[i][j] == 0) map[i][j] = num;
		for (i = fi + 1, j = fj; i < n  && map[i][j] != 1; i ++) 
			if (map[i][j] == 0) map[i][j] = num;
		for (i = fi - 1, j = fj; i >= 0 && map[i][j] != 1; i --) 
			if (map[i][j] == 0) map[i][j] = num;
	} else {
		for (i = 0; i < n; i ++) 
			for (j = 0; j < n; j ++) 
				if (map[i][j] == num) map[i][j] = 0; 
	}
}

void find(int x , int y , int p , int tot)
{
	if (tot > max) max = tot;
	if (x == n) return;
	if (y == n) { find(x + 1, 0, p, tot); return ;}
	if (map[x][y] == 0)
	{
		changeState(x, y, p, 0); 
		find(x , y + 1, p + 1, tot + 1);
		changeState(x, y, p, 1); 
	}
	find(x , y + 1, p, tot);
}

int main()
{
int i , j , x , y;
char a[4][5];

	while (scanf("%d" , &n) == 1)
	{
		if (n == 0) break;
		for (i = 0; i < n; i ++) scanf("%s" , a[i]);
		max = 0;
		for (i = 0; i < n; i ++)
			for (j = 0; j < n; j ++)
			{
				for (x = 0; x < n; x ++)
					for (y = 0; y < n; y ++)
						if (a[x][y] == '.') map[x][y] = 0;
						else map[x][y] = 1;
				find(i , j , 2, 0);
			}
		printf("%d\n" , max);
	}
	return 0;
}

• 第一个程序的DFS那里多了个else，所以就不同了... (3376) rovingcloud 2006-09-19 01:39:39
  • Re:第一个程序的DFS那里多了个else，所以就不同了... (21) Bter 2006-09-19 08:09:31