【习题 6-5 UVA-1600】Patrol Robot
习题 UVa Robot
2023-09-14 09:03:45 时间
【链接】 我是链接,点我呀:)
【题意】
【题解】
设dis[x][y][z]表示到(x,y)连续走了z个墙的最短路 bfs一下就ok【代码】
/*
1.Shoud it use long long ?
2.Have you ever test several sample(at least therr) yourself?
3.Can you promise that the solution is right? At least,the main ideal
4.use the puts("") or putchar() or printf and such things?
5.init the used array or any value?
6.use error MAX_VALUE?
7.use scanf instead of cin/cout?
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int k,n,m;
int a[N+10][N+10],dis[N+10][N+10][N+10];
queue <pair<int,pair<int,int> > > dl;
int main(){
#ifdef LOCAL_DEFINE
freopen("F:\\c++source\\rush_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
int T;
cin >> T;
while (T--){
cin >> n >> m;
cin >> k;
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
cin >> a[i][j];
memset(dis,255,sizeof dis);
dis[1][1][0] = 0;
dl.push(make_pair(1,make_pair(1,0)));
while (!dl.empty()){
pair <int,pair<int,int> > temp = dl.front();
int x = temp.first,y = temp.second.first,num = temp.second.second;
dl.pop();
for (int i = 0;i < 4;i++){
int tx = x+dx[i],ty = y + dy[i];
if (tx >=1 && tx <= n && ty >=1 && ty <= m){
if (a[tx][ty]){
int num1 = num+1;
if (num1 <= k){
if (dis[tx][ty][num1]==-1){
dis[tx][ty][num1] = dis[x][y][num] + 1;
dl.push(make_pair(tx,make_pair(ty,num1)));
}
}
}else{
int num1 = 0;
if (dis[tx][ty][num1]==-1){
dis[tx][ty][num1] = dis[x][y][num] + 1;
dl.push(make_pair(tx,make_pair(ty,num1)));
}
}
}
}
}
int ans = -1;
for (int i = 0;i <= k;i++)
if (dis[n][m][i]!=-1){
if (ans==-1){
ans = dis[n][m][i];
}else{
ans = min(ans,dis[n][m][i]);
}
}
cout << ans << endl;
}
return 0;
}
相关文章
- 【习题 4-7 UVA - 509】RAID!
- 【习题 8-20 UVA-1620】Lazy Susan
- 【习题 7-8 UVA-12107】Digit Puzzle
- 【习题 7-6 UVA - 12113】Overlapping Squares
- 【习题 6-9 UVA - 127】"Accordian" Patience
- 【习题 3-9 UVA - 10340】All in All
- 【习题 3-11 UVA - 1588】Kickdown
- 【习题5-5 UVA-10391】Compound Words
- 【习题5-3 UVA-10935】Throwing cards away I
- 【习题 3-1 UVA - 1585】Score
- 习题 3.9 有3个整数a,b,c,由键盘输入,输出其中最大的数。
- 习题 11.9 分别定义Teacher(教师)类和Cadre(干部)类,采用多重继承方式由这两个类派生出新类Teacher_Cadre(教师兼干部)类。
- 习题 7.1 写两个函数,分别求两个整数的最大公约数和最小公倍数,用主函数调用这两个函数,并输出结果。两个整数由键盘输入。
- 习题 2.4(2)依次将10个数输入,要求输出其中最大的数。
- 高等数学(第七版)同济大学 习题1-7 个人解答
- 高等数学(第七版)同济大学 习题10-1 个人解答
- 高等数学(第七版)同济大学 习题2-5 个人解答
- 字符串类习题、面试题具体解释(第二篇)