游客 注册 | 登录
中文 | En

3963 - B. 水管工

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

最近小仲迷上一个角水管工的游戏，游戏的大致规则是这样的，一块矩阵土地被分为M×N的单位正方形，每一个单位正方形要不都埋设一根水管或者种植了树木（种植树木的地方没有管道），水管将从坐标为（1,1）的左部边缘，延伸到坐标为（M，N）的右部边缘。水管只有两种，如下图所示：

       

每种管道将占据一个单位正方形土地，你可以旋转每个单元正方形上的管道，使其构成一个管道系统，即创造一条从（1,1）到（M，N）的连通管道。如下图

     

题目输入

每个测试案例的第一行有两个数，第1个数是M，第2个数是N，(N，M<25)，接着是M行数据，每一行有N个非负整数，每个整数表示地图中的每一小格的管道摆放方式，其中0表示树木，1~6分别表示管道的6中不同的摆放方式。

题目输出

如果从（1，1）能够有创建管道连通（M，N），则输出yes，否则输出，no way。

输入/输出样例

输入格式

5 4
5 3 5 3
1 5 3 0
2 3 5 1
6 1 1 5
1 5 5 4

2 2
1 2
1 1

2 2
1 1
1 1

输出格式

yes
no way
no way

C++解答

#include <iostream>
#include <string>
#include <algorithm>
#include <string.h>
using namespace std;

const int M = 20;
const int N = 20;

int maze[M][N];

int visited[M][N];


int m, n;
bool dfs(int row, int col, int pre)
{
	if (row == m && col == n + 1)
		return true;
	if (row <1 || row >m || col < 1 || col > n)
		return false;
	if (visited[row][col] == 1)
		return false;

	int cur = maze[row][col];
	if (maze[row][col] == 0)
		return false;

	visited[row][col] = 1;

	if (cur <= 4)
	{
		if (pre == 1 || pre == 3)
		{
			if (dfs(row, col + 1, 2))	return true;
			if (dfs(row, col - 1, 4))	return true;
		}
		if (pre == 2 || pre == 4)
		{
			if (dfs(row - 1, col, 3))	return true;
			if (dfs(row + 1, col, 1))	return true;
		}
	}
	else
	{
		if (pre == 1)
		{
			if (dfs(row + 1, col, pre))	return true;
		}
		if (pre == 2)
		{
			if (dfs(row, col + 1, pre))	return true;
		}
		if (pre == 3)
		{
			if (dfs(row - 1, col, pre))	return true;
		}
		if (pre == 4)
		{
			if (dfs(row, col - 1, pre))	return true;
		}
	}
	visited[row][col] = 0;
	return false;
}


int main()
{
	while (cin >> m >> n)
	{
		for (int i = 1; i <= m; i++)
		{
			for (int j = 1; j <= n; j++)
				cin >> maze[i][j];
		}
		memset(visited, 0, sizeof(visited));

		if (dfs(1, 1, 2))
			cout << "yes" << endl;
		else
			cout << "no way" << endl;

		//cout << ret;
	}

	return 0;
}

Java解答



import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;


public class Main{
	public static void main(String[] args) {
		Scanner input = new Scanner(new BufferedInputStream(System.in));
		while(input.hasNext()){
			int M = input.nextInt();
			int N = input.nextInt();
			int[][] arr = new int[M][N];
			for(int i = 0;i < M;i++)
				for(int j = 0;j < N;j++)
					arr[i][j] = input.nextInt();
			boolean[] booleanArr = new boolean[1];
			boolean[][] visitedArr = new boolean[M][N]; 
			booleanArr[0] = false;
			for (boolean[] bs : visitedArr) {
				Arrays.fill(bs, false);
			}
			findWay(arr,0,0,1,booleanArr,visitedArr);
			System.out.println(booleanArr[0] ? "yes" : "no way");
		}
	}
	private static void findWay(int[][] arr,int x,int y,int direction,boolean[] booleanArr,boolean[][] visitedArr){
		if(booleanArr[0])
			return;
		if(x == arr.length - 1 && y == arr[0].length){
			booleanArr[0] = true;
			return;
		}
		if(x < 0 || y < 0 || x >= arr.length || y >= arr[0].length || visitedArr[x][y])
			return;
		visitedArr[x][y] = true;
		switch(arr[x][y]){
		case 1:
		case 2:
		case 3:
		case 4:
			if(direction == 0 || direction == 2){
				findWay(arr,x,y - 1,3,booleanArr,visitedArr);
				findWay(arr,x,y + 1,1,booleanArr,visitedArr);
			}else{
				findWay(arr,x - 1,y,0,booleanArr,visitedArr);
				findWay(arr,x + 1,y,2,booleanArr,visitedArr);
			}
			break;
		case 5:
		case 6:
			if(direction == 0){
				findWay(arr,x - 1,y,direction,booleanArr,visitedArr);
			}else if(direction == 1){
				findWay(arr,x,y + 1,direction,booleanArr,visitedArr);
			}else if(direction == 2){
				findWay(arr,x + 1,y,direction,booleanArr,visitedArr);
			}else if(direction == 3){
				findWay(arr,x,y - 1,direction,booleanArr,visitedArr);
			}
			break;
		default:
		}
		visitedArr[x][y] = false;
	}
}
请先登陆