# 格点和斜线的方向向量，顺序要对应 d1 = [[-1, -1], [-1, 1], [1, 1], [1, -1]] d2 = [[-1, -1], [-1, 0], [0, 0], [0, -1]] chs = '\\/\\/' while T > 0: T = T - 1 r, c = map(int, input().split()) # 斜线 w = [''for _ inrange(r)] # 格点 dis = [[float('inf') for _ inrange(c + 1)] for _ inrange(r + 1)] vis = [[0for _ inrange(c + 1)] for _ inrange(r + 1)] for i inrange(r): w[i] = input() if (r + c) & 1: print('NO SOLUTION') continue q = deque() q.append((0, 0)) dis[0][0] = 0 while q: x, y = q.popleft() if x == r and y == c: break if vis[x][y]: continue vis[x][y] = 1 # 遍历 4 个方向的格点 for i inrange(4): nx = x + d1[i][0] ny = y + d1[i][1] if nx < 0or ny < 0or nx >= r+1or ny >= c+1: continue d = 0if chs[i] == w[x + d2[i][0]][y + d2[i][1]] else1 if dis[x][y] + d < dis[nx][ny]: q.append((nx, ny)) if d else q.appendleft((nx, ny)) dis[nx][ny] = dis[x][y] + d print(dis[r][c])
//a->b staticvoidadd(int a, int b, int c) { e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++; }
publicstaticvoidmain(String... args)throws Exception { PrintWriterout=newPrintWriter(newBufferedOutputStream(System.out)); BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in)); // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt"))); int[] in = read(br); N = in[0]; P = in[1]; K = in[2]; L = newint[P+1]; A = newint[P+1]; B = newint[P+1]; e = newint[2*P+1]; ne = newint[2*P+1]; w = newint[2*P+1]; h = newint[N+1]; for (inti=0; i < P; i++) { int[] t = read(br); A[i] = t[0]; B[i] = t[1]; L[i] = t[2]; } intleft=0, right = 1000000; intres= -1; while (left <= right) { intmid= left + (right-left)/2; if (bfs(mid)) { res = mid; right = mid - 1; } else { left = mid + 1; } } out.println(res); out.flush(); }
from collections import deque from typing importList
classSolution: defminCost(self, grid: List[List[int]]) -> int: # 顺序不能乱，1234 右左下上 dire = [(0, 1), (0, -1), (1, 0), (-1, 0)] n, m = len(grid), len(grid[0]) dis = [[float('inf') for _ inrange(m+1)] for _ inrange(n+1)] vis = [[0for _ inrange(m+1)] for _ inrange(n+1)] q = deque() q.append((0, 0)) dis[0][0] = 0 while q: x, y = q.popleft() if vis[x][y]: continue vis[x][y] = 1 for i inrange(4): nx, ny = x+dire[i][0], y+dire[i][1] if nx < 0or ny < 0or nx >= n or ny >= m: continue w = 0if (grid[x][y]-1) == i else1 if dis[nx][ny] > dis[x][y] + w: dis[nx][ny] = dis[x][y] + w q.append((nx, ny)) if w else q.appendleft((nx, ny)) return dis[n-1][m-1]
You are playing some computer game. One of its levels puts you in a maze consisting of lines, each of which contains cells. Each cell either is free or is occupied by an obstacle. The starting cell is in the row and column . In one step you can move one square up, left, down or right, if the target cell is not occupied by an obstacle. You can’t move beyond the boundaries of the labyrinth.
Unfortunately, your keyboard is about to break, so you can move left no more than times and move right no more than times. There are no restrictions on the number of moves up and down since the keys used to move up and down are in perfect condition.
Now you would like to determine for each cell whether there exists a sequence of moves that will put you from the starting cell to this particular one. How many cells of the board have this property?
Input
The first line contains two integers — the number of rows and the number columns in the labyrinth respectively.
The second line contains two integers — index of the row and index of the column that define the starting cell.
The third line contains two integers — the maximum allowed number of movements to the left and to the right respectively.
The next n lines describe the labyrinth. Each of them has length of m and consists only of symbols . and *. The -th character of the -th line corresponds to the cell of labyrinth at row and column . Symbol . denotes the free cell, while symbol * denotes the cell with an obstacle.
It is guaranteed, that the starting cell contains no obstacles.
Output
Print exactly one integer — the number of cells in the labyrinth, which are reachable from starting cell, including the starting cell itself.
Examples
45 32 12 ..... .***. ...** *....
out
10
解法一
很容易写错的一道题，不细想很可能写出下面的代码
import java.util.*; import java.io.*;
publicclassMain {
staticint N, M; staticint R, C; staticint X, Y; staticint[][] grid; staticboolean[][] vis; staticint[][] remainX, remainY; // 左右下上 staticint[][] dir = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
publicstaticvoidmain(String... args)throws Exception { PrintWriterout=newPrintWriter(newBufferedOutputStream(System.out)); BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in)); // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt"))); int[] nm = read(br); N = nm[0]; M = nm[1]; int[] rc = read(br); R = rc[0]; C = rc[1]; int[] xy = read(br); X = xy[0]; Y = xy[1];
// public class CF1063B_Labyrinth { // public static void main(String[] args) throws Exception { // for (int i = 0; i < 3; i++) { // new Main().main(); // } // } // }
“The Chamber of Secrets has been opened again” — this news has spread all around Hogwarts and some of the students have been petrified due to seeing the basilisk. Dumbledore got fired and now Harry is trying to enter the Chamber of Secrets. These aren’t good news for Lord Voldemort. The problem is, he doesn’t want anybody to be able to enter the chamber. The Dark Lord is going to be busy sucking life out of Ginny.
The Chamber of Secrets is an rectangular grid in which some of the cells are columns. A light ray (and a basilisk’s gaze) passes through the columns without changing its direction. But with some spell we can make a column magic to reflect the light ray (or the gaze) in all four directions when it receives the ray. This is shown in the figure below.
The basilisk is located at the right side of the lower right cell of the grid and is looking to the left (in the direction of the lower left cell). According to the legend, anyone who meets a basilisk’s gaze directly dies immediately. But if someone meets a basilisk’s gaze through a column, this person will get petrified. We know that the door to the Chamber is located on the left side of the upper left corner of the grid and anyone who wants to enter will look in the direction of its movement (in the direction of the upper right cell) from that position.
Given the dimensions of the chamber and the location of regular columns, Lord Voldemort has asked you to find the minimum number of columns that we need to make magic so that anyone who wants to enter the chamber would be petrified or just declare that it’s impossible to secure the chamber.
Input
The first line of the input contains two integer numbers n and m . Each of the next lines contains characters. Each character is either “.” or “#” and represents one cell of the Chamber grid. It’s “.” if the corresponding cell is empty and “#” if it’s a regular column.
Output
Print the minimum number of columns to make magic or -1 if it’s impossible to do.
Examples
33 .#. ... .#.
oUT
2
Note
The figure above shows the first sample test. In the first sample we should make both columns magic. The dragon figure represents the basilisk and the binoculars represent the person who will enter the Chamber of secrets. The black star shows the place where the person will be petrified. Yellow lines represent basilisk gaze moving through columns.
