SP22393 KATHTHI - KATHTHI
题面
题面翻译
给出一个的网格，每个位置有一个小写字母，初始在，每次可以向上下左右走，问走到的最小花费
设为当前位置，为下一位置。表示位置的字符。
若，则移动的花费为，否则花费为
提示：不要用某些“活着”的最短路算法
题目描述
Kathiresan is initially locked at cell (0,0) in a highly guarded rectangular prison of order RxC. He must reach the gate at (R-1,C-1) in order to escape from the prison. Kathiresan can move from any cell, to any of it's 4 adjacent cells (North, East, West and South). If Kathiresan is currently at (x1,y1), then he can move to (x2,y2) if and only if abs(x2-x1)+abs(y2-y1) == 1 and 0<=x2<R and 0<=y2<CKathiresan somehow manages to get the map of the prison.
If map[x1][y1] == map[x2][y2] then Kathiresan can move from (x1,y1) to (x2,y2) without killing any guards.
If map[x1][y1] != map[x2][y2], then Kathiresan can move from (x1,y1) to (x2,y2) by killing a guard.
Given the map of the prison, find the minimum number of guards Kathiresan must kill in order to escape from the prison.
Input:
The first line consists of an integer t, the number of test cases. For each test case, the first line consists of two integers R and C representing the order of the rectangular prison followed by R strings representing the map of the rectangular prison.
Output:
For each test case find the minimum number of guards Kathiresan must kill in order to escape from the prison.
Input Constraints:
1 <= t <= 10
2 <= R <= 1000
2 <= C <= 1000
'a' <= map[i][j] <= 'z'
Sample Input:
4
2 2
aa
aa
2 3
abc
def6 6akacccaaacfcamdfccaokhddzyxwdpzyxwdd5 5abbbcabaccaaaccaefcicdgdd Sample Output:
0
322输入格式
输出格式
样例 #1
样例输入 #1
4
2 2
aa
aa
2 3
abc
def
6 6
akaccc
aaacfc
amdfcc
aokhdd
zyxwdp
zyxwdd
5 5
abbbc
abacc
aaacc
aefci
cdgdd样例输出 #1
0
3
2
2思路
题面翻译看了不如不看。。。
这道题其实就是P4554的改版，就是数据范围大了些，导致原来建边的做法会TLE。
所以对于这种网格图，我们干脆就不建边了，直接用二维字符数组模拟。
其它的好像都和那道小明的游戏一模一样，是道 01BFS 的裸题，直接看代码吧。
代码
// #include<bits/stdc++.h>
// using namespace std;
// const int M=4e6+5000;
// char e[1050][1050];
// bool vis[M>>2];
// int t,n,m,cnt,sum;
// struct edge
// {
// int nxt,to,val;
// }ed[M];
// int fir[M>>2],dist[M>>2];
// void add(int u,int v,int w)
// {
// ed[++cnt].nxt=fir[u];
// ed[cnt].to=v;
// ed[cnt].val=w;
// fir[u]=cnt;
// }
// inline int read()
// {
// int x=0,y=1;//x是什么，y是正负
// char c=getchar();
// while(c>'9'||c<'0')
// {
// if(c=='-') y=-1;
// c=getchar();
// }
// while(c>='0'&&c<='9')
// {
// x=x*10+c-'0';
// c=getchar();
// }
// return x*y;
// }
// void _01BFS(int x)
// {
// for(int i=1;i<=sum;i++)
// {
// dist[i]=INT_MAX;
// vis[i]=false;
// }
// deque<int> q;
// dist[x]=0;
// q.push_back(x);
// vis[x]=true;
// while(q.size())
// {
// int p=q.front();
// q.pop_front();
// vis[p]=false;
// for(int i=fir[p];i;i=ed[i].nxt)
// {
// int v=ed[i].to;
// int d=dist[p]+ed[i].val;
// if(dist[v]>d)
// {
// dist[v]=d;
// if(!vis[v])
// {
// vis[v]=true;
// if(ed[i].val==0) q.push_front(v);
// else q.push_back(v);
// }
// }
// }
// }
// }
// int main()
// {
// char c;
// t=read();
// while(t--)
// {
// n=read(),m=read();
// sum=n*m;
// for(int i=1;i<=n;i++)
// for(int j=1;j<=m;j++)
// {
// while(c<'a'||c>'z') c=getchar();
// e[i][j]=c;
// c='\0';
// }
// for(int i=1;i<=n;i++)//建图
// for(int j=1;j<=m;j++)
// {
// int pos=(i-1)*m+j;
// if(i+1<=n) add(pos,pos+m,e[i][j]==e[i+1][j]?0:1);
// if(i-1>=1) add(pos,pos-m,e[i][j]==e[i-1][j]?0:1);
// if(j+1<=m) add(pos,pos+1,e[i][j]==e[i][j+1]?0:1);
// if(j-1>=1) add(pos,pos-1,e[i][j]==e[i][j-1]?0:1);
// }
// _01BFS(1);
// printf("%d\n",dist[sum]);
// // for(int i=1;i<=cnt;i++)
// // {
// // ed[i].to=0;
// // ed[i].val=0;
// // ed[i].nxt=0;
// // }
// memset(fir,0,sizeof(fir));
// // memset(e,'\0',sizeof(e));
// cnt=0;
// }
// return 0;
// }
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,t;
char e[N][N];
int dx[]={0,-1,0,1};
int dy[]={1,0,-1,0};
int dist[N][N];//原点到i，j的距离
struct point
{
int x,y,d;
point(){}
point(int a,int b,int c):x(a),y(b),d(c){}
};
void _01BFS()
{
deque<point> q;
q.push_front(point(1,1,0));
dist[1][1]=0;
while(!q.empty())
{
point now=q.front();
q.pop_front();
if(now.x==n&&now.y==m) break;
for(int i=0;i<4;i++)
{
int nx=now.x+dx[i],ny=now.y+dy[i];
if(nx<1||nx>n||ny<1||ny>m) continue;
if(e[now.x][now.y]==e[nx][ny]&&now.d<dist[nx][ny])
{
dist[nx][ny]=now.d;
q.push_front(point(nx,ny,dist[nx][ny]));
}
if(e[now.x][now.y]!=e[nx][ny]&&now.d+1<dist[nx][ny])
{
dist[nx][ny]=now.d+1;
q.push_back(point(nx,ny,dist[nx][ny]));
}
}
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
memset(dist,0x3f,sizeof(dist));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",e[i]+1);
_01BFS();
printf("%d\n",dist[n][m]);
}
}