Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:迭代加深水过

Posted by sjdeak at 2016-12-18 07:41:28 on Problem 3009
In Reply To:迭代加深水过 Posted by:CuriousCat at 2016-09-15 09:13:27
> #include <cstdio>
> #include <cstring>
> #include <algorithm>
> #define MAX_N 205
> 
> using namespace std;
> 
> int grid[MAX_N][MAX_N], N, M, ans;
> 
> bool dfs(int x, int y, int deep, int maxDeep) {
> 	static const int xc[] = { 1,0,0,-1 };
> 	static const int yc[] = { 0,-1,1,0 };
> 
> 	if (deep >= maxDeep) return false;
> 	for (int i = 0;i < 4;++i) {
> 		int nx = x, ny = y;
> 		while (grid[nx + xc[i]][ny + yc[i]] == 0)
> 			nx = nx + xc[i], ny = ny + yc[i];
> 		if (grid[nx + xc[i]][ny + yc[i]] == 3) return true;
> 		if ((grid[nx + xc[i]][ny + yc[i]] == -1) ||
> 			(nx == x && ny == y)) continue;
> 		grid[nx + xc[i]][ny + yc[i]] = 0;
> 		if (dfs(nx, ny, deep + 1, maxDeep)) return true;
> 		grid[nx + xc[i]][ny + yc[i]] = 1;
> 	}
> 	return false;
> }
> 
> int main(int argc, char *argv[]) {
> 	while (scanf("%d%d", &M, &N) == 2 && N != 0 && M != 0) {
> 		int ans = -1, bx, by;
> 		memset(grid, -1, sizeof(grid));
> 		for (int i = 1;i <= N;++i)
> 			for (int j = 1;j <= M;++j) {
> 				scanf("%d", &grid[i][j]);
> 				if (grid[i][j] == 2) {
> 					bx = i, by = j;
> 					grid[i][j] = 0;
> 				}
> 			}
> 		for (int k = 1;k <= 10;++k)
> 			if (dfs(bx, by, 0, k)) {
> 				ans = k;
> 				break;
> 			}
> 		printf("%d\n", ans);
> 	}
> 	return 0;
> }
多谢了,写的真好

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator