【LeetCode】刷题代码记录

2
5 5 2
1 1
..##.
#..#.
.##..
.##..
#.##.
1 2
3 1
5 5 3
1 1
...#.
.#...
....#
..##.
...#.
3 3
4 1
2 4

-1
9

from queue import Queue
import sys
dir = [[0,1],[0,-1],[1,0],[-1,0]]
class Solution:
    def start(self,mp,x,y,xi,yi):
        Q = Queue()
        steps = Queue()
        Q.put([x,y])
        steps.put(0)
        for line in mp:
            print(line)
        print("from ({},{}) to ({},{})".format(x,y,xi,yi))
        vis = [[ 0 for i in range(self.m+1) ] for j in range(self.n+1)]
        print(len(vis),len(vis[0]))
        while Q.empty() == False:
            now = Q.get()
            step = steps.get()
            print('now {} {} {}'.format(now[0],now[1],step))
            if now[0] == xi and now[1] == yi:
                mp[now[0]][now[1]] == '.'
                self.x = now[0]
                self.y = now[1]
                mp[xi][yi] = '.'
                return step-1
            for d in dir:
                newx = now[0] + d[0]
                newy = now[1] + d[1]
                if newx <=0 or newy <= 0 or newx >self.n or newy >self.m:
                    continue
                if newx == xi and newy == yi or mp[newx][newy] == '.':
                    if vis[newx][newy] == 1:
                        continue
                    # print("add {} {}".format(newx,newy))
                    vis[newx][newy] = 1
                    Q.put([newx,newy])
                    steps.put(step+1)
        return -1
        
    def run(self,n,m,k,mp,bomb_list):
        cost = 0
        for target in bomb_list:
            res = self.start(mp,self.x,self.y,target[0],target[1])
            print("step",res)
            if res != -1:
                cost += res
            else:
                print(-1)
                return
        print("cost:",cost)

    def stdin(self):
        self.n,self.m,k = list(map(int,input().split()))
        self.x,self.y = list(map(int,input().split()))
        mp = [['#'] * (self.m+1)]
        for i in range(self.n):
            line = list(input())
            line.insert(0,'#')
            mp.append(line)
        
        bomb_list = []
        for i in range(k):
            xi,yi = list(map(int,input().split()))
            bomb_list.append([xi,yi])
            mp[xi][yi] = 'x'
        
        self.run(self.n,self.m,k,mp,bomb_list)
    
        

with open(r"2.in", 'r') as file:
    sys.stdin = file
    s1 = Solution()
    T = int(input())
    while T>0:
        s1.stdin()
        T-=1

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if prices == []:
            return 0
        day_num = len(prices)
        leftmin = [9999] * day_num # 左侧的最小值
        rightmax = [0] * day_num # 右侧的最大值
        leftmin[0] = prices[0]
        rightmax[-1] = prices[-1]
        for i in range(1,day_num):
            leftmin[i] = min(leftmin[i-1],prices[i])
            rightmax[day_num-i-1] = max(rightmax[day_num-i],prices[day_num-i-1])
        max_price = 0
        print(leftmin,'\n',rightmax)
        for i in range(day_num):
            max_price = max(max_price,rightmax[i]-leftmin[i])
        return max_price

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        inf = int(1e9)
        minprice = inf
        maxprofit = 0
        for price in prices:
            maxprofit = max(price - minprice, maxprofit)
            minprice = min(price, minprice)
        return maxprofit

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        pre_price = 0
        profit = 0
        min_price = 1e9
        for price in prices:
            print(max_profit)
            if price < pre_price:
                #当天的价格下跌，则前一天需要卖出
                min_price = price
                max_profit = max_profit + profit
                profit = 0
            else:
                min_price = min(min_price,price)
                profit = price - min_price
            pre_price = price
        # 假如到最后一天没有出现下降，需要计算利润
        max_profit = max_profit + profit
        return max_profit