Eric - 用户 - Liuser's OJ

斗宗
排名 72
距离下一等级斗尊还需AC 78 题

通过 422 题积分 1500

不显示

Ericzc2011@qq.com

本人的博客

博客

人生就像打电话，不是你先挂，就是我先挂。

十年寒窗，高考复读班；百日苦战，考不上大专。

行云流水，堪称完美

用户名

666

Eric

#include<bits/stdc++.h>

using namespace std;

int n,m;
short g[110][110];
int dp[110][110];

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,-1,0};

int dfs(int x,int y,int bs,bool magic,int color)
{
	if(x == n && y == n)
	{
		int p = magic;
		if(g[nx][ny] != 0 && g[nx][ny] != color) p ++;
		dp[x][y] = 0;
		return bs;
	}
	if(dp[x][y] != 0x3f3f3f3f) return bs + dp[x][y];
	for(int i = 0;i < 4;i ++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if(nx >= 1 && nx <= n && ny >= 1 && ny <= n)
		{
			if(magic && !g[nx][ny]) continue;
			int p = magic;
			if(g[nx][ny] != 0 && g[nx][ny] != color) p ++;
			if(!g[nx][ny]) dp[x][y] = min(dp[x][y],dfs(nx,ny,p + 1,true,0) - magic);
			else dp[x][y] = min(dp[x][y],dfs(nx,ny,p,false,g[nx][ny]) - magic);
		}
	}
	return bs + dp[x][y];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(dp,0x3f,sizeof(dp));
	cin >> n >> m;
	for(int i = 1;i <= m;i ++)
	{
		int x,y,z;
		cin >> x >> y >> z;
		g[x][y] = z + 1;
	}
	long long ans = dfs(1,1,0,false,g[1][1]);
	if(ans == 0x3f3f3f3f) cout << -1;
	else cout << dp[1][1];
	for(int i = 1;i <= n;i ++)
	{
		for(int j = 1;j <= n;j ++)
		{
			cout << dp[i][j] << " ";
		}
		cout << "\n";
	}
	return 0;
}

2022-03-28 20:33:46

←上一年下一年→

较少

较多

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 62 63 64 65 66 67 71 72 73 78 86 89 101 102 112 119 121 132 133 134 141 169 173 174 177 178 179 200 201 205 206 212 213 219 220 237 239 240 250 256 259 260 261 262 263 264 265 273 274 275 278 504 506 519 525 549 723 1000 1008 1014 1019 1025 1033 1040 1042 1043 1044 1050 1051 1053 1054 1058 1073 1078 1079 1080 1081 1087 1091 1092 1108 1109 1110 1111 1115 1116 1117 1118 1119 1131 1132 1133 1156 1158 1159 1160 1165 1186 1197 1202 1203 1205 1208 1209 1210 1216 1230 1240 1241 1247 1252 1253 1256 1257 1258 1259 1261 1262 1271 1273 1279 1280 1288 1296 1298 1299 1320 1322 1323 1324 1334 1337 1343 1346 1347 1349 1359 1361 1364 1370 1371 1372 1374 1467 1468 1469 1470 1471 1472 1552 1567 1899 1924 1949 1954 2028 2075 2083 2088 2091 2095 2096 2099 2271 2400 2408 2434 2453 2461 2462 3196 3200 3201 3203 3204 3553 3554 3570 3572 3851 3865 3874 3877 3878 3891 3895 3896 3904 3911 3912 3916 3920 3921 3968 3969 3973 4039 4159 4160 4161 4162 4180 4181 4240 4900 4901 4902 4903 4904 4905 4906 4907 4908 4909 4910 4911 4912 4913 4915 4917 4919 4920 4921 4922 4923 4924 4925 4926 4927 4929 4934 5003 5005 5024 5025 5106 5111 5126 5278 5501 5502 5503 5504 5505 5506 5507 5508 5509 5510 5511 5512 5513 5514 5515 5516 5517 5518 5519 5520 5521 5522 5523 5524 5525 5526 5527 5528 5529 5530 5531 5532 5533 5534 5535 5536 5537 5538 5539 5540 5541 5542 5543 5544 5545 5546 5773 6000 6001 6002 6003 6004 6005 6006 6007 6008 6009 6010 6011 6012 6013 6014 6015 6016 6017 6018 6019 6020 6021 6022 6023 6024 6025 6026 6027 6028 6029 6030 6031 6070 6108 6117 6127 6134 6254 6277 6292 6296 6305 6312 6324 6332 6333 6334 6335 6401 6402 6403 6404 6442 6445 6446 6448 6501 6508 6509 6538 6553 6554 6561 6567 6649 6650 6658 6673 8095 8096 8386 8387 8421 8422 8423 8484

61 68 69 74 75 79 96 120 165 210 222 242 255 725 1026 1029 1039 1072 1075 1290 1332 1348 2100 2101 2102 3213 3423 4928 5047 6043 6049 6315 6325 6507 6612 8097

标题	时间
bbbbbbbbbb	2023-03-13 20:59:57
Hallo World的奇葩写法	2023-07-19 10:35:48
11	2023-12-26 20:44:25
atcoder abc342 D	2024-05-04 11:48:05
发现错误	2024-05-12 18:13:19
植物大战僵尸c++	2024-05-12 18:56:20
11111	2024-05-18 11:15:55
11	2024-06-17 21:11:35
有没有想要easyx二维游戏或者unity三维FPS游戏的	2024-07-22 18:00:29
# 看抽奖前排	2024-08-06 12:38:06
# 某某人解密爆了	2024-08-10 16:29:31
这个题难度是不是标错了	2024-08-31 17:26:27
运行这个程序	2024-09-03 16:40:47
55分提示	2024-09-03 17:33:07
@root 建议加一道水紫	2024-09-12 17:24:00
求助	2024-09-13 14:19:40
发现一个好玩的	2024-09-14 14:21:41
发现水蓝	2024-09-14 21:54:23
发现bug	2024-09-20 12:42:16
距离CSP还剩1Hours。警钟长鸣	2024-09-21 8:45:57
距离CSP-S还剩2Hours。警钟长鸣	2024-09-21 12:36:43
CSP-J1 2024 试题及答案	2024-09-21 12:47:44
发现牛逼洛谷账户	2024-09-21 13:12:23
CSP-S 2024 试题及答案	2024-09-21 21:49:47
喜报	2024-09-27 14:25:13
给大家一个好东西	2024-09-28 16:46:49

比赛	名次	积分
初始积分		1500

作业	时间
周六晚18:30（10.28）	2023-10-28 16:24:49
第一周python作业（杨杨老师2022秋季班周六上午10:30）	2022-09-10 10:14:15
C++第三次作业	2019-03-23 9:43:13
C++第二次作业	2019-03-23 9:43:13
C++第一次作业	2019-03-23 9:43:13

真实姓名

Email

个性签名

本人的博客

注册于

统计

练习情况